这道题目是维护边权信息，于是我就把原树中边变成点维护。由于颜色不超过30种，可以每个点维护一个int整数代表自己子树的颜色集合，pushup时并(就是 | 这个运算符)一下即可。对于每个原树中的点，颜色一定要保持为0。pushdown时，要判断一下，使得原树中的点颜色始终保持为0，不能被修改，不然就会出错。具体实现见代码。
接下来就好办了，操作1就先cut再link，操作2就先提取这段路径再打懒标，操作3就先提取路径再求一下颜色总数即可。
至于操作1的判断祖孙关系，暂时不知道怎么快速判断，于是我只好在原树中暴力判断，结果居然过了。。。事实上，当树变得很高时，我的打法会被卡。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=
50005;
int n,m,op,u,v,c,cnt,ans,pa[N],rt[N];
int fa[N*
2],ch[N*
2][
2],rev[N*
2],tag[N*
2],sumv[N*
2],siz[N*
2],val[N*
2],stk[N*
2];
int head[N*
2],to[N*
4],nxt[N*
4];
void adde(
int u,
int v){to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void dfs(
int u){
int v;
for(
int i=head[u];i;i=nxt[i]){v=to[i];
if(v!=fa[u]){fa[v]=u;dfs(v);}}
}
bool isroot(
int u){
return ch[fa[u]][
0]!=u&&ch[fa[u]][
1]!=u;
}
int which(
int u){
return u==ch[fa[u]][
1];
}
void pushup(
int u){sumv[u]=
1<<val[u];siz[u]=
1;
if(ch[u][
0]){sumv[u]|=sumv[ch[u][
0]];siz[u]+=siz[ch[u][
0]];}
if(ch[u][
1]){sumv[u]|=sumv[ch[u][
1]];siz[u]+=siz[ch[u][
1]];}
}
void reverse(
int u){rev[u]^=
1;swap(ch[u][
0],ch[u][
1]);
}
void maintain(
int u,
int c){tag[u]=c;sumv[u]=
1<<c;
if(u>n){val[u]=c;}
}
void downtag(
int u){
if(rev[u]){
if(ch[u][
0]){reverse(ch[u][
0]);}
if(ch[u][
1]){reverse(ch[u][
1]);}rev[u]=
0;}
if(tag[u]){
if(ch[u][
0]){maintain(ch[u][
0],tag[u]);}
if(ch[u][
1]){maintain(ch[u][
1],tag[u]);}tag[u]=
0;}
}
void pushdown(
int u){stk[stk[
0]=
1]=u;
for(;!isroot(u);u=fa[u]){stk[++stk[
0]]=fa[u];}
while(stk[
0]){downtag(stk[stk[
0]--]);}
}
void rotate(
int x){
int y=fa[x],z=fa[y],md=which(x);
if(!isroot(y)){ch[z][which(y)]=x;}fa[x]=z;ch[y][md]=ch[x][!md];fa[ch[y][md]]=y;ch[x][!md]=y;fa[y]=x;pushup(y);pushup(x);
}
void splay(
int u){pushdown(u);
while(!isroot(u)){
if(!isroot(fa[u])){rotate(which(fa[u])==which(u)?fa[u]:u);}rotate(u);}
}
void access(
int u){
for(
int v=
0;u;v=u,u=fa[u]){splay(u);ch[u][
1]=v;pushup(u);}
}
void makeroot(
int u){access(u);splay(u);reverse(u);
}
void link(
int u,
int v){makeroot(u);fa[u]=v;
}
void cut(
int u,
int v){makeroot(u);access(v);splay(v);fa[u]=ch[v][
0]=
0;pushup(v);
}
bool judge(
int u,
int v){
while(v){
if(u==v){
return false;}v=pa[v];}
return true;
}
bool isconnect(
int u,
int v){
if(u==v){
return true;}makeroot(u);access(v);splay(v);
return fa[u]!=
0;
}
int main(){
while(~
scanf(
"%d%d",&n,&m)){
memset(fa,
0,
sizeof(fa));
memset(ch,
0,
sizeof(ch));
memset(rev,
0,
sizeof(rev));
memset(tag,
0,
sizeof(tag));
memset(sumv,
0,
sizeof(sumv));
memset(siz,
0,
sizeof(siz));
memset(val,
0,
sizeof(val));
memset(head,
0,
sizeof(head));rt[
0]=cnt=
0;
for(
int i=
1;i<=n;i++){
scanf(
"%d",&pa[i]);
if(pa[i]){adde(pa[i],i+n);adde(i+n,pa[i]);adde(i,i+n);adde(i+n,i);}
else{rt[++rt[
0]]=i;}}
for(
int i=
1;i<=n;i++){
scanf(
"%d",&val[i+n]);sumv[i+n]=
1<<val[i+n];siz[i]=siz[i+n]=
1;}
for(
int i=
1;i<=rt[
0];i++){dfs(rt[i]);}
for(
int i=
1;i<=m;i++){
scanf(
"%d%d%d",&op,&u,&v);
if(op==
1){
scanf(
"%d",&c);
if(judge(u,v)){
if(pa[u]){cut(pa[u],u+n);cut(u+n,u);}pa[u]=v;link(pa[u],u+n);link(u+n,u);splay(u+n);val[u+n]=c;pushup(u+n);}}
else if(op==
2){
scanf(
"%d",&c);
if(u!=v&&isconnect(u,v)){makeroot(u);access(v);splay(v);maintain(v,c);}}
else{
if(u==v||!isconnect(u,v)){
puts(
"0 0");}
else{makeroot(u);access(v);splay(v);ans=
0;
for(
int j=
1;j<=
30;j++){
if(sumv[v]&(
1<<j)){ans++;}}
printf(
"%d %d\n",(siz[v]-
1)/
2,ans);}}}}
return 0;
}
转载于:https://www.cnblogs.com/2016gdgzoi471/p/9476908.html
总结
以上是生活随笔为你收集整理的【uva11994】Happy Painting!【LCT】的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
