题目大意：
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段）
思路:
树剖之后，维护其两端的颜色、答案和标记即可。
代码：
#include<cstdio> #include<iostream> #define N 100001 using namespace std; int n,m,cnt,dfn,vis[N],head[N],to[N<<1],next[N<<1],deep[N],size[N],top[N],id[N],v[N],pa[N],lazy[N<<2],lc[N<<2],rc[N<<2],sum[N<<2]; void ins(int x,int y) { to[++cnt]=y,next[cnt]=head[x],head[x]=cnt; } void dfs1(int x) { size[x]=vis[x]=1; for (int i=head[x];i;i=next[i]) if (!vis[to[i]]) { deep[to[i]]=deep[x]+1; pa[to[i]]=x; dfs1(to[i]); size[x]+=size[to[i]]; } } void dfs2(int x,int chain) { int k=0,i; id[x]=++dfn; top[x]=chain; for (i=head[x];i;i=next[i]) if (deep[to[i]]>deep[x] && size[to[i]]>size[k]) k=to[i]; if (!k) return; dfs2(k,chain); for (i=head[x];i;i=next[i]) if (deep[to[i]]>deep[x] && to[i]!=k) dfs2(to[i],to[i]); } void build(int l,int r,int cur) { sum[cur]=1,lazy[cur]=-1; if(l==r)return; int mid=l+r>>1; build(l,mid,cur<<1),build(mid+1,r,cur<<1|1); } void update(int k) { lc[k]=lc[k<<1],rc[k]=rc[k<<1|1]; if (rc[k<<1]^lc[k<<1|1]) sum[k]=sum[k<<1]+sum[k<<1|1]; else sum[k]=sum[k<<1]+sum[k<<1|1]-1; } void pushdown(int l,int r,int k) { int tmp=lazy[k]; lazy[k]=-1; if (tmp==-1 || l==r) return; sum[k<<1]=sum[k<<1|1]=1; lazy[k<<1]=lazy[k<<1|1]=tmp; lc[k<<1]=rc[k<<1]=tmp; lc[k<<1|1]=rc[k<<1|1]=tmp; } void change(int L,int R,int l,int r,int cur,int val) { if (l==L && r==R) { lc[cur]=rc[cur]=val; sum[cur]=1; lazy[cur]=val; return; } int mid=L+R>>1; pushdown(L,R,cur); if (r<=mid) change(L,mid,l,r,cur<<1,val); else if (l>mid) change(mid+1,R,l,r,cur<<1|1,val); else change(L,mid,l,mid,cur<<1,val),change(mid+1,R,mid+1,r,cur<<1|1,val); update(cur); } int ask(int L,int R,int l,int r,int cur) { if (l==L && r==R) return sum[cur]; int mid=L+R>>1; pushdown(L,R,cur); if (r<=mid) return ask(L,mid,l,r,cur<<1); else if (l>mid) return ask(mid+1,R,l,r,cur<<1|1); else { int tmp=1; if (rc[cur<<1]^lc[cur<<1|1]) tmp=0; return ask(L,mid,l,mid,cur<<1)+ask(mid+1,R,mid+1,r,cur<<1|1)-tmp; } } int getc(int l,int r,int cur,int x) { if (l==r) return lc[cur]; int mid=l+r>>1; pushdown(l,r,cur); if (x<=mid) return getc(l,mid,cur<<1,x); else return getc(mid+1,r,cur<<1|1,x); } int solvesum(int x,int y) { int sum=0; for (;top[x]!=top[y];x=pa[top[x]]) { if (deep[top[x]]<deep[top[y]]) swap(x,y); sum+=ask(1,n,id[top[x]],id[x],1); if (getc(1,n,1,id[top[x]])==getc(1,n,1,id[pa[top[x]]])) sum--; } if (deep[x]>deep[y]) swap(x,y); return sum+=ask(1,n,id[x],id[y],1); } void solvechange(int x,int y,int val) { for (;top[x]!=top[y];x=pa[top[x]]) { if (deep[top[x]]<deep[top[y]]) swap(x,y); change(1,n,id[top[x]],id[x],1,val); } if (deep[x]>deep[y]) swap(x,y); change(1,n,id[x],id[y],1,val); } int main() { int i,a,b,c; scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%d",&v[i]); for(i=1;i<n;i++) scanf("%d%d",&a,&b),ins(a,b),ins(b,a); dfs1(1),dfs2(1,1),build(1,n,1); for(i=1;i<=n;i++) change(1,n,id[i],id[i],1,v[i]); for(i=1;i<=m;i++) { char ch[10]; scanf("%s",ch); if(ch[0]=='Q') { scanf("%d%d",&a,&b); printf("%d\n",solvesum(a,b)); } else { scanf("%d%d%d",&a,&b,&c); solvechange(a,b,c); } } return 0; }
转载于:https://www.cnblogs.com/HHshy/p/5823378.html
相关资源：JAVA上百实例源码以及开源项目