漂亮小姐姐点击就送：https://www.luogu.org/problemnew/show/P2486
题目描述
输入输出格式
输入格式：
输出格式：
对于每个询问操作，输出一行答案。
输入输出样例
说明
//终于写出来了 //不难的题 我太zz了 //就是让着维护一个带修改的查询相同区间有几个的题 //记录每个节点掌控的子树的左端点的颜色和右端点的颜色 //左端点颜色=左孩子左端点颜色 右端点颜色=右孩子右端点颜色 //root->lcol=root->lson->lcol root->rcol=root->rson->rcol //如果左儿子的右端点颜色和右儿子的左端点颜色相同，那么这个区间段数-- //root->sum=root->lson->sum+root->rson->sum-(root->lson->rcol==root->rson->lcol) //查询的时候，要记录两条路径上上一次查询的左端点的颜色 //如果这一次查询的右端点颜色和上一次查询的左端点颜色相同，则--ans //到最后两点公共祖先一样（在一条链上）的时候，要分别减两次 //也就是左边的链减一次，右边的链也减一次 //update的时候不要忘了更新lcol和rcol //自己写的时候没改。。。然后。。。。。。 //Modify的时候不用像查询一样那么麻烦，普通修改就行 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+5; int n,m; int a,b,c; int head[N],num_edge; struct Edge { int v,nxt; }edge[N<<1]; struct NODE { int fa,son; int size,dep; int s,t; int top; }node[N]; struct TREE { TREE *lson,*rson; int l,r,mid; int sum,lcol,rcol; int lazy; }tree[N<<2]; typedef TREE* Tree; Tree Root,now_node=tree; inline int read() { char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f; } inline void add_edge(int u,int v) { edge[++num_edge].v=v; edge[num_edge].nxt=head[u]; head[u]=num_edge; } void dfs1(int u) { node[u].size=1; for(int i=head[u],v;i;i=edge[i].nxt) { v=edge[i].v; if(v==node[u].fa) continue; node[v].dep=node[u].dep+1; node[v].fa=u; dfs1(v); node[u].size+=node[v].size; if(node[v].size>node[node[u].son].size) node[u].son=v; } } int bound; void dfs2(int u,int top) { node[u].s=++bound; node[u].top=top; if(node[u].son) { dfs2(node[u].son,top); for(int i=head[u],v;i;i=edge[i].nxt) { v=edge[i].v; if(node[u].son==v||v==node[u].fa) continue; dfs2(v,v); } } node[u].t=bound; } void build(Tree &root,int l,int r) { root=++now_node; root->l=l,root->r=r,root->mid=l+r>>1; if(l==r) return; build(root->lson,l,root->mid); build(root->rson,root->mid+1,r); } void pushdown(const Tree &root) { if(root->lazy) { root->lson->lcol=root->lson->rcol=root->lazy; root->rson->lcol=root->rson->rcol=root->lazy; root->lson->lazy=root->rson->lazy=root->lazy; root->lson->sum=root->rson->sum=1; root->lazy=0; } } void update(const Tree &root,int l,int r,int col) { if(root->l==l&&root->r==r) { root->lcol=root->rcol=col; root->lazy=col; root->sum=1; return; } pushdown(root); if(r<=root->mid) update(root->lson,l,r,col); else if(l>root->mid) update(root->rson,l,r,col); else { update(root->lson,l,root->mid,col); update(root->rson,root->mid+1,r,col); } root->sum=root->lson->sum+root->rson->sum; root->lcol=root->lson->lcol; root->rcol=root->rson->rcol; if(root->lson->rcol==root->rson->lcol) --root->sum; } int query_sum(Tree &root,int l,int r) { if(root->l==l&&root->r==r) return root->sum; pushdown(root); if(r<=root->mid) return query_sum(root->lson,l,r); else if(l>root->mid) return query_sum(root->rson,l,r); else { int ans=query_sum(root->lson,l,root->mid)+query_sum(root->rson,root->mid+1,r); if(root->lson->rcol==root->rson->lcol) return ans-1; else return ans; } } int query_col(Tree &root,int pos) { if(root->l==root->r) return root->lcol; pushdown(root); if(pos<=root->mid) return query_col(root->lson,pos); else return query_col(root->rson,pos); } inline void Modify(int x,int y,int col) { int fx=node[x].top,fy=node[y].top; while(fx!=fy) { if(node[fx].dep>node[fy].dep) { update(Root,node[fx].s,node[x].s,col); x=node[fx].fa; fx=node[x].top; } else { update(Root,node[fy].s,node[y].s,col); y=node[fy].fa; fy=node[y].top; } } if(node[x].dep>node[y].dep) update(Root,node[y].s,node[x].s,col); else update(Root,node[x].s,node[y].s,col); } inline int Query(int x,int y) { int fx=node[x].top,fy=node[y].top; int ans=0,nx=0,ny=0,tmp; while(fx!=fy) { if(node[fx].dep>node[fy].dep) { ans+=query_sum(Root,node[fx].s,node[x].s); tmp=query_col(Root,node[x].s); if(tmp==nx) --ans; nx=query_col(Root,node[fx].s); x=node[fx].fa; fx=node[x].top; } else { ans+=query_sum(Root,node[fy].s,node[y].s); tmp=query_col(Root,node[y].s); if(tmp==ny) --ans; ny=query_col(Root,node[fy].s); y=node[fy].fa; fy=node[y].top; } } if(node[x].dep>node[y].dep) { ans+=query_sum(Root,node[y].s,node[x].s); tmp=query_col(Root,node[y].s); if(tmp==ny) --ans; tmp=query_col(Root,node[x].s); if(tmp==nx) --ans; return ans; } else { ans+=query_sum(Root,node[x].s,node[y].s); tmp=query_col(Root,node[x].s); if(tmp==nx) --ans; tmp=query_col(Root,node[y].s); if(tmp==ny) --ans; return ans; } } int col[N]; char s[10]; int main() { n=read(),m=read(); for(int i=1;i<=n;++i) col[i]=read(); for(int i=1;i<n;++i) { a=read(),b=read(); add_edge(a,b); add_edge(b,a); } dfs1(1); dfs2(1,1); build(Root,1,n); for(int i=1;i<=n;++i) update(Root,node[i].s,node[i].s,col[i]); for(int i=1;i<=m;++i) { scanf("%s",s); if(s[0]=='C') { a=read(),b=read(),c=read(); Modify(a,b,c); } else { a=read(),b=read(); printf("%d ",Query(a,b)); } } return 0; } /* 6 5 1 1 1 1 2 2 1 2 2 3 3 4 4 5 5 6 Q 1 6 */