这个题还是树剖的基本练习，不过线段树维护的东西复杂了一些。
还是树剖起手，之后我们要在线段树中维护当前区间内颜色个数，最靠左的颜色和最靠右的颜色。这样的话我们在合并的时候，如果左区间最靠右颜色和右区间最靠左颜色是相同的话，那么这个合并之后的区间的颜色个数要-1（因为原来计算的方法是左右两区间之和）。
然后在修改和查询的时候也一样，修改没啥好说的，查询的话因为我写的是三段式查询，在最后一种情况的时候，因为答案也需要合并所以需要像上面所说的一样判断一次。至于pushdown的话，这个无需担心，因为pushdown一定是完全包括的，所以直接把下一级区间的颜色个数赋为1，左右颜色为当前区间颜色即可。
最后要注意的就是在沿着链上跳的时候，两个链的相交处需要判断一下颜色是否相同，如果相同答案-1.
然后这个题我就G了，原因是我线段树传参传错了……
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 200005; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct seg { int v,lazy,lcol,rcol; }t[M<<2]; struct edge { int next,to,from; }e[M<<1]; int n,m,dfn[M],rk[M],a[M],size[M],dep[M],fa[M],hson[M],q,x,y,head[M],ecnt,idx,top[M],z; char s[5]; void add(int x,int y) { e[++ecnt].to = y; e[ecnt].next = head[x]; head[x] = ecnt; } void dfs1(int x,int f,int depth) { size[x] = 1,fa[x] = f,dep[x] = depth; int maxson = -1; for(int i = head[x];i;i = e[i].next) { if(e[i].to == f) continue; dfs1(e[i].to,x,depth+1); size[x] += size[e[i].to]; if(size[e[i].to] > maxson) maxson = size[e[i].to],hson[x] = e[i].to; } } void dfs2(int x,int t) { dfn[x] = ++idx,rk[idx] = a[x],top[x] = t; if(!hson[x]) return; dfs2(hson[x],t); for(int i = head[x];i;i = e[i].next) { if(e[i].to == fa[x] || e[i].to == hson[x]) continue; dfs2(e[i].to,e[i].to); } } void update(int p) { t[p].v = t[p<<1].v + t[p<<1|1].v; if(t[p<<1].rcol == t[p<<1|1].lcol) t[p].v--; t[p].lcol = t[p<<1].lcol,t[p].rcol = t[p<<1|1].rcol; } void build(int p,int l,int r) { if(l == r) { t[p].v = 1; t[p].lcol = t[p].rcol = rk[l]; return; } int mid = (l+r) >> 1; build(p<<1,l,mid),build(p<<1|1,mid+1,r); update(p); } void pushdown(int p,int l,int r) { if( l == r ) while(1); t[p<<1].v = t[p<<1|1].v = 1; t[p<<1].rcol = t[p<<1].lcol = t[p<<1|1].rcol = t[p<<1|1].lcol = t[p].lazy; t[p<<1].lazy = t[p<<1|1].lazy = t[p].lazy; t[p].lazy = 0; } int acol(int p,int l,int r,int pos) { if(l == r) return t[p].lcol; int mid = (l+r) >> 1; if(t[p].lazy) pushdown(p,l,r); if(pos <= mid) return acol(p<<1,l,mid,pos); else return acol(p<<1|1,mid+1,r,pos); } int query(int p,int l,int r,int kl,int kr) { int ans = 0,pcol,qcol; if(l == kl && r == kr) return t[p].v; int mid = (l+r) >> 1; if(t[p].lazy) pushdown(p,l,r); if(kr <= mid) ans += query(p<<1,l,mid,kl,kr); else if(kl > mid) ans += query(p<<1|1,mid+1,r,kl,kr); else { ans += query(p<<1,l,mid,kl,mid),ans += query(p<<1|1,mid+1,r,mid+1,kr); pcol = acol(1,1,n,mid),qcol = acol(1,1,n,mid+1); if(pcol == qcol) ans--; } return ans; } void modify(int p,int l,int r,int kl,int kr,int col) { if(l == kl && r == kr) { t[p].v = 1; t[p].lcol = t[p].rcol = t[p].lazy = col; return; } int mid = (l+r) >> 1; if(t[p].lazy) pushdown(p,l,r); if(kr <= mid) modify(p<<1,l,mid,kl,kr,col); else if(kl > mid) modify(p<<1|1,mid+1,r,kl,kr,col); else modify(p<<1,l,mid,kl,mid,col),modify(p<<1|1,mid+1,r,mid+1,kr,col); update(p); } int qrange(int x,int y) { int ans = 0,pcol,qcol; while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x,y); ans += query(1,1,n,dfn[top[x]],dfn[x]); pcol = acol(1,1,n,dfn[top[x]]),qcol = acol(1,1,n,dfn[fa[top[x]]]); if(pcol == qcol) ans--; x = fa[top[x]]; } if(dep[x] > dep[y]) swap(x,y); ans += query(1,1,n,dfn[x],dfn[y]); return ans; } void mrange(int x,int y,int z) { while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x,y); modify(1,1,n,dfn[top[x]],dfn[x],z); x = fa[top[x]]; } if(dep[x] > dep[y]) swap(x,y); modify(1,1,n,dfn[x],dfn[y],z); } int main() { n = read(),m = read(); rep(i,1,n) a[i] = read(); rep(i,1,n-1) x = read(),y = read(),add(x,y),add(y,x); dfs1(1,0,1),dfs2(1,1),build(1,1,n); while(m--) { scanf("%s",s); if(s[0] == 'Q') { x = read(),y = read(); printf("%d ",qrange(x,y)); } else if(s[0] == 'C') { x = read(),y = read(),z = read(); mrange(x,y,z); } } return 0; }