题目（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;
}
Comments NOTHING