考试一共四个半小时，光这道题就打了三个小时。。然后又改了俩小时才过。我太蒟蒻了。
其实数据结构这种题就看第一遍打没打顺，顺了就A了，要是再找错再改就慢了，而且样例过了不能说明任何问题（虽然考试的时候我连样例都没出hhh）
给树按上三个新域，一个是左边的颜色，一个是右边的颜色，一个是颜色段数。
void pushup(int root){ tree[root].lcol=tree[root<<1].lcol; tree[root].rcol=tree[root<<1|1].rcol; if(tree[root<<1].rcol==tree[root<<1|1].lcol) tree[root].duan=tree[root<<1].duan+tree[root<<1|1].duan-1; else tree[root].duan=tree[root<<1].duan+tree[root<<1|1].duan;}
这段pushup想必大家就明白怎么递归了。
注意在往上爬的过程当中，一段一段中间的连接区域可能会有颜色相同，需要判断一下，找出fx。
完整代码：
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;#define N 500000#define pos(i,a,b) for(int i=(a);i<=(b);i++)int n,m;int v[N];struct haha{ int next,to;}edge[N];int head[N],cnt=1;struct qian{ int left,right; int lcol,rcol,duan;}tree[N];int duan[N];void add(int u,int v){ edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++;}int rt[N];int size[N],son[N],dep[N],fa[N];void dfs1(int x){ size[x]=1;son[x]=0; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; if(to!=fa[x]) { fa[to]=x; dep[to]=dep[x]+1; dfs1(to); size[x]+=size[to]; if(size[to]>size[son[x]]) son[x]=to; } }}int id[N],pos[N],top[N];int ji;void dfs2(int x,int tp){ top[x]=tp; id[x]=++ji; pos[ji]=x; if(son[x]) dfs2(son[x],tp); for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; if(to!=fa[x]&&to!=son[x]) dfs2(to,to); }}void pushup(int root){ tree[root].lcol=tree[root<<1].lcol; tree[root].rcol=tree[root<<1|1].rcol; if(tree[root<<1].rcol==tree[root<<1|1].lcol) tree[root].duan=tree[root<<1].duan+tree[root<<1|1].duan-1; else tree[root].duan=tree[root<<1].duan+tree[root<<1|1].duan;}void build(int left,int right,int root){ rt[root]=-1; tree[root].left=left; tree[root].right=right; if(left==right) { tree[root].lcol=tree[root].rcol=v[pos[left]]; tree[root].duan=1; return; } int mid=(left+right)>>1; build(left,mid,root<<1); build(mid+1,right,root<<1|1); pushup(root);}void pushdown(int root){ if(rt[root]>=0) { rt[root<<1]=rt[root]; rt[root<<1|1]=rt[root]; tree[root<<1].lcol=tree[root<<1].rcol=rt[root]; tree[root<<1|1].lcol=tree[root<<1|1].rcol=rt[root]; tree[root<<1].duan=tree[root<<1|1].duan=1; rt[root]=-1; }}void change(int left,int right,int num,int root){ if(left<=tree[root].left&&right>=tree[root].right) { rt[root]=num; tree[root].lcol=tree[root].rcol=num; tree[root].duan=1; return; } pushdown(root); int mid=(tree[root].right+tree[root].left)>>1; if(left<=mid) change(left,right,num,root<<1); if(right>mid) change(left,right,num,root<<1|1); pushup(root);}int query(int left,int right,int root){ if(left<=tree[root].left&&right>=tree[root].right) return tree[root].duan; pushdown(root); int mid=(tree[root].left+tree[root].right)>>1; if(right<=mid) return query(left,right,root<<1); else if(left>mid) return query(left,right,root<<1|1); else { int tmp=1; if(tree[root<<1].rcol!=tree[root<<1|1].lcol) tmp=0; return query(left,mid,root<<1)+query(mid+1,right,root<<1|1)-tmp; }}int temp1,temp2;void check(int po,int root){ pushdown(root); if(tree[root].left==tree[root].right) { temp1=tree[root].lcol; return; } int mid=(tree[root].right+tree[root].left)>>1; if(po<=mid) check(po,root<<1); else check(po,root<<1|1);}void check2(int po,int root){ pushdown(root); if(tree[root].left==tree[root].right) { temp2=tree[root].lcol; return; } int mid=(tree[root].right+tree[root].left)>>1; if(po<=mid) check2(po,root<<1); else check2(po,root<<1|1);}int erx,fux,ery,fuy;int Query(int x,int y){ int fx=top[x],fy=top[y]; int ans=0; while(fx!=fy) { if(dep[fx]>dep[fy]) { check(id[fa[fx]],1); check2(id[fx],1); ans+=query(id[fx],id[x],1); if(temp1==temp2) ans--; x=fa[fx]; fux=x; erx=fx; fx=top[x]; } else { check(id[fa[fy]],1); check2(id[fy],1); ans+=query(id[fy],id[y],1); if(temp1==temp2) ans--; y=fa[fy]; fuy=y; ery=fy; fy=top[y]; } } if(dep[x]>dep[y]) { //check(id[erx],1); //check(id[fux],1); ans+=query(id[y],id[x],1); //if(temp1==temp2) //ans--; } else { //check(id[ery],1); //check(id[fuy],1); ans+=query(id[x],id[y],1); //if(temp1==temp2) //ans--; } return ans;}void Change(int x,int y,int z){ int fx=top[x],fy=top[y]; while(fx!=fy) { if(dep[fx]<dep[fy]) { swap(fx,fy); swap(x,y); } change(id[fx],id[x],z,1); x=fa[fx];fx=top[x]; } if(dep[x]>dep[y]) swap(x,y); change(id[x],id[y],z,1);}int read(){ int su=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch<='9'&&ch>='0') { su=su*10+ch-'0'; ch=getchar(); } return su;}int main(){ //freopen("paint6.in","r",stdin); //freopen("paint66.out","w",stdout); scanf("%d%d",&n,&m); pos(i,1,n) v[i]=read(); pos(i,1,n-1) { int x,y; x=read();y=read(); add(x,y); add(y,x); } dfs1(1); dfs2(1,1); build(1,n,1); pos(i,1,m) { char p; int x,y,z; scanf("%s",&p); if(p=='C') { x=read();y=read();z=read(); Change(x,y,z); } if(p=='Q') { x=read();y=read(); printf("%d\n",Query(x,y)); } } //while(1); return 0;}
