這道題目是維護(hù)邊權(quán)信息，于是我就把原樹中邊變成點(diǎn)維護(hù)。由于顏色不超過30種，可以每個(gè)點(diǎn)維護(hù)一個(gè)int整數(shù)代表自己子樹的顏色集合，pushup時(shí)并(就是 | 這個(gè)運(yùn)算符)一下即可。對于每個(gè)原樹中的點(diǎn)，顏色一定要保持為0。pushdown時(shí)，要判斷一下，使得原樹中的點(diǎn)顏色始終保持為0，不能被修改，不然就會(huì)出錯(cuò)。具體實(shí)現(xiàn)見代碼。
接下來就好辦了，操作1就先cut再link，操作2就先提取這段路徑再打懶標(biāo)，操作3就先提取路徑再求一下顏色總數(shù)即可。
至于操作1的判斷祖孫關(guān)系，暫時(shí)不知道怎么快速判斷，于是我只好在原樹中暴力判斷，結(jié)果居然過了。。。事實(shí)上，當(dāng)樹變得很高時(shí)，我的打法會(huì)被卡。
代碼:
#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;
}
轉(zhuǎn)載于:https://www.cnblogs.com/2016gdgzoi471/p/9476908.html
總結(jié)
以上是生活随笔為你收集整理的【uva11994】Happy Painting!【LCT】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
