题意：
给出2个操作， 第一个操作。更改x->y的路径点的权值为w
第二个操作，查询这段路径上有多少段不同的颜色
思路：
之前做过一道染色的题，和这题类似，但是当时是给出点的权值，此题是给出边的权值，按如下代码的操作两题是无差别的。
时刻记录左右端点，按线段树的思想来逐步去掉相同颜色的值
#include <map> #include <set> #include <queue> #include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; const int MAXN = 50005; struct node { int left,right; int left_color,right_color; int sum; int lazy; }t[MAXN*4]; struct Edge { int to,next; } edge[MAXN*4]; struct ed { int x,y,val; }e[MAXN*4]; int pre[MAXN]; int fa[MAXN],son[MAXN],siz[MAXN],dep[MAXN],top[MAXN],id[MAXN],val[MAXN]; int n,q; int col[MAXN]; int topw= 0; int tot ,head[MAXN]; int cnt=0; void Init() { topw = 0; memset(head,-1,sizeof(head)); memset(son,0,sizeof(son)); } void addedge(int u,int v ) { edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++; } void dfs1(int u,int f,int d) { dep[u]=d; siz[u]=1; son[u]=0; fa[u]=f; for(int i =head[u]; i!=-1; i=edge[i].next) { int v=edge[i].to; if(v==fa[u]) continue; dfs1(v,u,d+1); siz[u]+=siz[v]; if(siz[son[u]]<siz[v]) son[u]=v; } } void dfs2(int u,int tp) { top[u]=tp; id[u]=++topw; pre[topw]=u; if(son[u]) dfs2(son[u],tp); for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].to; if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } } void push_up(int i) { t[i].sum=t[i<<1].sum+t[i<<1|1].sum; if(t[i<<1].right_color==t[i<<1|1].left_color) t[i].sum--; t[i].right_color=t[i<<1|1].right_color; t[i].left_color=t[i<<1].left_color; } void push_down(int i) { if(t[i].lazy) { t[i<<1|1].lazy=t[i<<1].lazy=t[i].lazy; t[i<<1].left_color=t[i<<1].right_color=t[i].lazy; t[i<<1|1].left_color=t[i<<1|1].right_color=t[i].lazy; t[i<<1|1].sum=t[i<<1].sum=t[i].sum; t[i].lazy=0; } } void build(int i,int left,int right) { t[i].left=left,t[i].right=right,t[i].lazy=0; if(left==right) { t[i].left_color=val[left]; t[i].right_color=val[left]; t[i].sum=1; return ; } int mid=(t[i].left+t[i].right)>>1; build(i<<1,left,mid); build(i<<1|1,mid+1,right); push_up(i); return ; } void update(int i,int left,int right,int w) { if(left<=t[i].left&&t[i].right<=right) { t[i].lazy=w; t[i].left_color=t[i].right_color=w; t[i].sum=1; return ; } push_down(i); int mid=(t[i].left+t[i].right)>>1; if(mid>=left) { update(i<<1,left,right,w); } if(mid<right) { update(i<<1|1,left,right,w); } push_up(i); } int right_color = 0; int ANS = 0; node query(int i,int left,int right) { if(left<=t[i].left&&t[i].right<=right) { return t[i]; } push_down(i); int mid=(t[i].left+t[i].right)>>1; if(right<=mid) return query(i<<1,left,right); else if(left>mid) { return query(i<<1|1,left,right); } else { node p1=query(i<<1,left,mid); node p2=query(i<<1|1,mid+1,right); node res; res.sum=p1.sum+p2.sum; res.left_color=p1.left_color; res.right_color=p2.right_color; if(p1.right_color==p2.left_color) res.sum--; return res; } push_up(i); } void change(int u,int v,int w) { int tpu=top[u],tpv=top[v]; while(tpu!=tpv) { if(dep[tpu]<dep[tpv]) { swap(u,v); swap(tpu,tpv); } update(1,id[tpu],id[u],w); u=fa[tpu]; tpu=top[u]; } if(u==v) return ; if(dep[u]>dep[v]) swap(u,v); update(1,id[son[u]],id[v],w); } int ask(int u,int v) { int ans=0; int c1=-1,c2=-1; int tpu=top[u],tpv=top[v]; while(tpu!=tpv) { if(dep[tpu]<dep[tpv]) { swap(u,v); swap(tpu,tpv); swap(c1,c2); } node tmp=query(1,id[tpu],id[u]); ans+=tmp.sum; if(tmp.right_color==c1) ans--; c1=tmp.left_color; u=fa[tpu]; tpu=top[u]; } if(u==v) { if(c1==c2) ans--; return ans; } if(dep[u]<dep[v]) { swap(u,v); swap(c1,c2); } node tmp=query(1,id[son[v]],id[u]); ans+=tmp.sum; if(tmp.left_color==c2) ans--; if(tmp.right_color==c1) ans--; return ans; } int main() { while(~scanf("%d%d",&n,&q)) { topw=0,cnt=0; memset(son,0,sizeof(son)); memset(edge,0,sizeof(edge)); memset(head,-1,sizeof(head)); int u,v,a,b,c; for(int i=1;i<n;i++) { scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].val); addedge(e[i].x,e[i].y); addedge(e[i].y,e[i].x); } topw=0; dfs1(1,0,1); dfs2(1,1); for(int i = 1 ; i < n ; i++) { if(dep[e[i].x]<dep[e[i].y]) swap(e[i].x,e[i].y); val[id[e[i].x]]=e[i].val; } build(1,1,topw); char op[5]; int color; while(q--) { scanf("%s",op) ; if(op[0] == 'C') { scanf("%d %d %d",&u,&v,&color); change(u,v,color); } else { scanf("%d %d",&u,&v); if(u==v) { printf("0\n"); continue; } int ans = 0; ans += ask(u,v); printf("%d\n",ans); } } } } /* 4 5 1 2 1 2 3 2 2 4 2 Q 3 4 C 1 2 2 Q 2 3 */