[bzoj2243]-[SDOI2011]染色

也不知多久之前看过这题……当时还没学树剖


题目(bzoj)
题目(洛谷)
这题其实也没什么好说的……
主要是考虑区间合并时每个区间两端的颜色是否相同,相同的话ans–
完毕。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>
#define ll long long
#define llmax LONG_LONG_MAX
#define llmin LONG_LONG_MIN
#define ls id<<1
#define rs id<<1|1
#define inf INT_MAX
#define readf(f) scanf("%lf",&f)
#define N 100005
using namespace std;
template <class _E> inline void read(_E &e)
{
	e=0;bool ck=0;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')ck=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
	if(ck)e=-e;
}
int n,M;
struct edge{int vk;int nxt;}e[N*2];
struct Segment_tree{int l;int r;int cnt;int lc;int rc;int lazy;}t[N<<2];
int tt,head[N];
inline void ad(int u,int v){e[++tt].vk=v;e[tt].nxt=head[u];head[u]=tt;}
int c[N];
int dep[N],siz[N],rank[N],son[N],f[N],top[N],pre[N],idx;
void dfs1(int u,int fa)
{
	siz[u]=1;f[u]=fa;
	for (int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].vk;
		if (v==fa) continue;
		dep[v]=dep[u]+1;
		dfs1(v,u);
		siz[u]+=siz[v];
		if (!son[u] || siz[v]>siz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int fa)
{
	top[u]=fa;
	rank[u]=++idx;pre[rank[u]]=u;
	if (!son[u]) return;
	dfs2(son[u],fa);
	for (int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].vk;
		if (v==f[u] || v==son[u]) continue;
		dfs2(v,v);
	}
}
inline void up(int id)
{
	t[id].lc=t[ls].lc,t[id].rc=t[rs].rc;
	t[id].cnt=t[ls].cnt+t[rs].cnt;
	if (t[ls].rc==t[rs].lc) --t[id].cnt;
}
inline void down(int id)
{
	if (t[id].lazy)
	{
		t[ls].lazy=t[rs].lazy=t[id].lazy;
		t[ls].cnt=t[rs].cnt=1;
		t[ls].lc=t[ls].rc=t[id].lc;
		t[rs].lc=t[rs].rc=t[id].lc;
		t[id].lazy=0;
	}
}
void build(int l,int r,int id)
{
	t[id].l=l,t[id].r=r;t[id].cnt=0;
	if (l==r)
		return;
	int mid=(l+r)>>1;
	build(l,mid,ls),build(mid+1,r,rs);
}
void update(int col,int l,int r,int id)
{
	int L=t[id].l,R=t[id].r;
	if (L==l && R==r)
	{
		t[id].cnt=t[id].lazy=1;
		t[id].lc=t[id].rc=col;
		return;
	}
	down(id);
	int mid=(L+R)>>1;
	if (r<=mid) update(col,l,r,ls);
	else if (l>mid) update(col,l,r,rs);
	else update(col,l,mid,ls),update(col,mid+1,r,rs);
	up(id);
}
int lcol,rcol;
int query(int l,int r,int id,int L,int R)
{
	int L1=t[id].l,R1=t[id].r;
	if (L1==L) lcol=t[id].lc;
	if (R1==R) rcol=t[id].rc;
	if (L1==l && R1==r) return t[id].cnt;
	down(id);
	int mid=(L1+R1)>>1;
	if (r<=mid) return query(l,r,ls,L,R);
	else if (l>mid) return query(l,r,rs,L,R);
	else
	{
		int ret=query(l,mid,ls,L,R)+query(mid+1,r,rs,L,R);
		if (t[ls].rc==t[rs].lc) --ret;
		return ret;
	}
}
inline void change(int x,int y,int col)
{
	int f1=top[x],f2=top[y];
	while (f1!=f2)
	{
		if (dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);
		update(col,rank[f1],rank[x],1);
		x=f[f1];f1=top[x];
	}
	if (dep[x]>dep[y]) swap(x,y);
	update(col,rank[x],rank[y],1);
}
inline int qans(int x,int y)
{
	int a1=-1,a2=-1,ret=0;
	int f1=top[x],f2=top[y];
	while (f1!=f2)
	{
		if (dep[f1]<dep[f2]) swap(x,y),swap(f1,f2),swap(a1,a2);
		ret+=query(rank[f1],rank[x],1,rank[f1],rank[x]);
		if (rcol==a1) --ret;
		a1=lcol;
		x=f[f1];f1=top[x];
	}
	if (dep[x]<dep[y]) swap(x,y),swap(a1,a2);
	ret+=query(rank[y],rank[x],1,rank[y],rank[x]);
	if (a1==rcol) --ret;
	if (a2==lcol) --ret;
	return ret;
}
int main()
{
	read(n);read(M);
	for (int i=1;i<=n;++i) read(c[i]);
	for (int i=1;i<n;++i)
	{
		int x,y;
		read(x),read(y);
		ad(x,y),ad(y,x);
	}
	dfs1(1,0);dfs2(1,1);
	build(1,n,1);
	for (int i=1;i<=n;++i)
		update(c[i],rank[i],rank[i],1);
	while (M--)
	{
		char ch[1];
		int aa,bb,cc;
		scanf("%s",ch);
		if (ch[0]=='C')
		{
			read(aa),read(bb),read(cc);
			change(aa,bb,cc);
		}
		else
		{
			read(aa),read(bb);
			printf("%d\n",qans(aa,bb));
		}
	}
	return 0;
}

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注