震驚！LCT還能這么用！

這個顏色修改的特點是點到根

搜刮一下性質，顏色從根到某個點是分層次單調增的，而且同一個點的兩個不同兒子不會有相同顏色，也就是相同顏色的點是樹上自上往下的一條鏈

前面這些都是次要的，主要是能不能想到并不和LCT的access操作很像

那么我們可以讓一棵splay維護一條相同顏色的鏈，那么access修改兒子的時候順便改一改點到根的顏色數(shù)

dfs序+線段樹維護子樹中的最大值

第二個問直接暴力跳鏈算就行了

#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; const int _=1e2; const int maxn=1e5+_; const int fbin=(1<<17)+_; const int mbit=30; int n;int L[maxn],R[maxn]; struct segnode{int mx,la;}; struct segtree {segnode tr[2*fbin];void pushdown(int now){int lc=(now<<1),rc=(now<<1|1);if(tr[now].la!=0){tr[lc].mx+=tr[now].la,tr[lc].la+=tr[now].la;tr[rc].mx+=tr[now].la,tr[rc].la+=tr[now].la;tr[now].la=0;}}void update(int now){int lc=(now<<1),rc=(now<<1|1);tr[now].mx=max(tr[lc].mx,tr[rc].mx);}void change(int now,int ql,int qr,int l,int r,int c){if(ql==l&&qr==r){tr[now].mx+=c,tr[now].la+=c;return ;}pushdown(now);int mid=(ql+qr)/2,lc=(now<<1),rc=(now<<1|1);if(r<=mid) change(lc,ql,mid,l,r,c);else if(mid+1<=l)change(rc,mid+1,qr,l,r,c);else change(lc,ql,mid,l,mid,c),change(rc,mid+1,qr,mid+1,r,c);update(now);}int getmax(int now,int ql,int qr,int l,int r){if(ql==l&&qr==r)return tr[now].mx;pushdown(now);int mid=(ql+qr)/2,lc=(now<<1),rc=(now<<1|1);if(r<=mid) return getmax(lc,ql,mid,l,r);else if(mid+1<=l)return getmax(rc,mid+1,qr,l,r);else return max(getmax(lc,ql,mid,l,mid),getmax(rc,mid+1,qr,mid+1,r));} }S;struct trnode{int f,son[2];bool fz;}; struct LCT {trnode tr[maxn];void rev(int x){if(tr[x].fz){int lc=tr[x].son[0],rc=tr[x].son[1];swap(tr[lc].son[0],tr[lc].son[1]),tr[lc].fz^=1;swap(tr[rc].son[0],tr[rc].son[1]),tr[rc].fz^=1;tr[x].fz=false;}}void rotate(int x,int w){int f=tr[x].f,ff=tr[f].f;int R,r;R=f,r=tr[x].son[w];tr[R].son[1-w]=r;if(r!=0)tr[r].f=R;R=ff,r=x;if(tr[ff].son[0]==f)tr[R].son[0]=r;else if(tr[ff].son[1]==f)tr[R].son[1]=r;tr[r].f=R;R=x,r=f;tr[R].son[w]=r;tr[r].f=R;}int tlen,tmp[maxn];bool islight(int x){if(tr[x].f==0||(tr[tr[x].f].son[0]!=x&&tr[tr[x].f].son[1]!=x))return true;return false;}void splay(int x,int rt){tlen=0;int i=x;while(x!=rt&& !islight(i) )tmp[++tlen]=i,i=tr[i].f;tmp[++tlen]=i;while(tlen!=0)rev(tmp[tlen]),tlen--;while(tr[x].f!=rt&& !islight(x) ){int f=tr[x].f,ff=tr[f].f;if(ff==rt||islight(f)){if(tr[f].son[0]==x)rotate(x,1);else rotate(x,0);}else{if(tr[ff].son[0]==f&&tr[f].son[0]==x)rotate(f,1),rotate(x,1);else if(tr[ff].son[1]==f&&tr[f].son[1]==x)rotate(f,0),rotate(x,0);else if(tr[ff].son[0]==f&&tr[f].son[1]==x)rotate(x,0),rotate(x,1);else if(tr[ff].son[1]==f&&tr[f].son[0]==x)rotate(x,1),rotate(x,0);}}}//~~~~~~~~~~~~~~~~~~~~~~~~~~splay~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ int findroot(int x){splay(x,0);while(tr[x].son[0]!=0)x=tr[x].son[0];return x;}void access(int x){int y=0,u,rt;while(x!=0){splay(x,0);u=tr[x].son[1];if(y!=0)rt=findroot(y),S.change(1,1,n,L[rt],R[rt],-1);splay(x,0);tr[x].son[1]=y;if(u!=0)rt=findroot(u),S.change(1,1,n,L[rt],R[rt],1);y=x,x=tr[x].f;}}//~~~~~~~~~~~~~~~~~~~~~~~~~~lct~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~int getsum(int x,int z){int ans=1;while(findroot(x)!=findroot(z)){splay(x,0);x=tr[x].f;ans++;}return ans;}//~~~~~~~~~~~~~~~~~~~~~~~~~~~~solve~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ }lct;//--------------------------------------------data structure--------------------------------------------------------------struct node {int x,y,next; }a[2*maxn];int len,last[maxn]; void ins(int x,int y) {len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len; } int z,f[mbit][maxn],dep[maxn]; void dfs(int x) {for(int i=1;(1<<i)<=dep[x];i++)f[i][x]=f[i-1][f[i-1][x]];L[x]=++z;for(int k=last[x];k;k=a[k].next){int y=a[k].y;if(y!=f[0][x]){lct.tr[y].f=x;dep[y]=dep[x]+1;f[0][y]=x;dfs(y);}}R[x]=z;S.change(1,1,n,L[x],R[x],1); } int LCA(int x,int y) {if(dep[x]<dep[y])swap(x,y);for(int i=25;i>=0;i--)if(dep[x]-dep[y]>=(1<<i))x=f[i][x];if(x==y)return x;for(int i=25;i>=0;i--)if(dep[x]>=(1<<i)&&f[i][x]!=f[i][y])x=f[i][x],y=f[i][y];return f[0][x]; }//---------------------------------------true tree------------------------------------------------------------int main() {freopen("a.in","r",stdin);freopen("a.out","w",stdout);int Q,x,y;scanf("%d%d",&n,&Q); len=1;for(int i=1;i<n;i++){scanf("%d%d",&x,&y);ins(x,y),ins(y,x);}dfs(1);int op;while(Q--){scanf("%d",&op);if(op==1){scanf("%d",&x);lct.access(x);}else if(op==2){scanf("%d%d",&x,&y);int z=LCA(x,y);printf("%d\n",lct.getsum(x,z)+lct.getsum(y,z)-1);}else{scanf("%d",&x);printf("%d\n",S.getmax(1,1,n,L[x],R[x]));}}return 0; }

?

轉載于:https://www.cnblogs.com/AKCqhzdy/p/10453207.html

總結

以上是生活随笔為你收集整理的bzoj4817: [Sdoi2017]树点涂色的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。