[关闭]
@11101001 2018-03-24T13:32:57.000000Z 字数 3212 阅读 865

bzoj4817: [Sdoi2017]树点涂色

题目链接

bzoj4817: [Sdoi2017]树点涂色

题解

数据结构.....大概很容易看出是道lct 然后弃疗
操作1很想lct里面的access操作
那么对于操作2
设F[i]=i点到lct根路径上的splay数（也就是虚边数）+1
那么对于操作2的(x,y)
ans(x,y)=F[x]+F[y]-(F(lca(x,y)))+1;
对于操作3的(x),就是在x的子树中取max，我们可以用dfs序+线段树维护
考虑操作1对操作3的影响
在access的时候，当一个边由虚变实，此时该边所连的深度大的点的颜色种类-1
反之当一边由实变虚，此时该边所连的深度大的点的颜色种类+1
trick:保存当前节点在树中最左儿子的编号用以修改区间(即left[])
ps:中途电脑爆炸,然后重码QAQ，心态爆炸

代码

  1. /*
  2.  *
  3.  * 数据结构+LCT+SEG_TREE
  4.  *  
  5.  */
  7. #include<cstdio>
  8. #include<algorithm>
  9. const int maxn = 100007;
  10. int n,m;
  11. struct node{
  12.     int v,next;
  13. }edge[maxn<<1];
  14. int head[maxn],num;
  15. void Add_Edge(int u,int v) {
  16.     edge[++num].v=v;edge[num].next=head[u];head[u]=num;
  17. }
  18. int idfn[maxn],ldfn[maxn],rdfn[maxn],f[maxn][20],dep[maxn];
  19. int cnt=0,fa[maxn];
  20. void dfs(int u,int F) {
  21.     idfn[ldfn[u]=++cnt]=u,f[u][0]=fa[u]=F;
  22.     for(int i=head[u];i;i=edge[i].next) {
  23.         int v=edge[i].v;
  24.         if(v!=F) dep[v]=dep[u]+1,dfs(v,u);
  25.     }
  26.     rdfn[u]=cnt;
  27.     return ;
  28. }
  29. int LCA(int x,int y) {
  30.     if(dep[x]<dep[y]) std::swap(x,y);
  31.     for(int i=dep[x]-dep[y],j=0;i;i>>=1,++j)
  32.         if(i&1)x=f[x][j];
  33.     if(x==y) return x;
  34.     for(int i=19;~i;--i) 
  35.         if(f[x][i]!=f[y][i]) 
  36.             x=f[x][i],y=f[y][i];
  37.     return f[x][0];
  38. }
  39. class Segment_Tree {
  40. #define lc x<<1
  41. #define rc x<<1|1
  42.     private :
  44.         struct Node {
  45.             int max,tag;
  46.             Node () : tag(0){}
  47.         };
  48.         Node t[maxn<<2];
  50.         void update(int x) {
  51.             t[x].max=std::max(t[lc].max,t[rc].max);
  52.         }
  53.         void push_down(int x) {
  54.             if(!t[x].tag)return;
  55.             int k=t[x].tag;
  56.             t[lc].max+=k;
  57.             t[lc].tag+=k;
  58.             t[rc].max+=k;
  59.             t[rc].tag+=k;
  60.             t[x].tag=0;
  61.             return ;
  62.         }
  64.     public :
  66.         void build (int x,int l,int r) {
  67.             if(l==r) {
  68.                 t[x].max=dep[idfn[l]]+1;return;
  69.             }
  70.             int mid=l+r>>1;
  71.             build(lc,l,mid);
  72.             build(rc,mid+1,r);
  73.             return update(x);
  74.         }
  76.         void modify(int x,int l,int r,int L,int  R,int w) {
  77.             if(L<=l&&R>=r) {
  78.                 t[x].tag+=w;t[x].max+=w;
  79.                 return ;
  80.             }
  81.             push_down(x);
  82.             int mid=l+r>>1;
  83.             if(mid>=L) modify(lc,l,mid,L,R,w);
  84.             if(mid<R) modify(rc,mid+1,r,L,R,w);
  85.             return update(x);
  86.         }
  88.         int query(int x,int l,int r,int L,int  R) {
  89.             if(L<=l&&R>=r) 
  90.                 return t[x].max;
  91.             push_down(x);
  92.             int mid=l+r>>1,ans=0;
  93.             if(mid>=L) ans=std::max(ans,query(lc,l,mid,L,R));
  94.             if(mid<R) ans=std::max(ans,query(rc,mid+1,r,L,R));
  95.             return ans;
  96.         }
  97. #undef lc
  98. #undef rc
  99. }SEG_T;
  100. class Link_Cut_tree {
  101. #define lc ch[x][0]
  102. #define rc ch[x][1]
  103.     private : 
  105.         int ch[maxn][2],left[maxn];
  106.     void update(int x) {
  107.         left[x]=lc ? left[lc]:x;
  108.     }
  110.     bool isroot(int x) {
  111.         return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
  112.     }
  114.     void rotate(int x) {
  115.         int y=fa[x],z=fa[y],d=(ch[y][1]==x)^1;
  116.         if(!isroot(y)) ch[z][ch[z][1]==y]=x;fa[x]=z;
  117.         ch[y][d^1]=ch[x][d],fa[ch[x][d]]=y;
  118.         ch[x][d]=y;fa[y]=x;
  119.         update(y),update(x);
  120.     }
  122.     void splay(int x) {
  123.         while(!isroot(x)) {
  124.             int y=fa[x],z=fa[y];
  125.             if(!isroot(y)) {
  126.                 if(ch[y][1]==x^ch[z][1]==y) rotate(x);
  127.                 else rotate(y);
  128.             }
  129.             rotate(x);
  130.         }
  131.     }
  132.     public:
  134.         void init() {
  135.             dfs(1,0),SEG_T.build(1,1,n);
  136.             for(int i=1;i<=n;++i) left[i]=i;
  137.             for(int j=1;j<20;j++)
  138.                 for(int i=1;i<=n;i++)
  139.                     f[i][j]=f[f[i][j-1]][j-1];
  140.         }
  142.         void access(int x) {
  143.             for(int t=0;x;x=fa[t=x]) {
  144.                 splay(x);
  145.                 if(rc) SEG_T.modify(1,1,n,ldfn[left[rc]],rdfn[left[rc]],1);
  146.                 rc=t;
  147.                 if(rc) SEG_T.modify(1,1,n,ldfn[left[rc]],rdfn[left[rc]],-1);
  148.             }
  149.             return ;
  150.         }
  152.         int query(int x) {
  153.             int ans=0;
  154.             for(;x;x=fa[x],ans++)splay(x);
  155.             return ans;
  156.         }
  158.         int query(int u,int v) {
  159.             return query(u)+query(v)-2*query(LCA(u,v))+1;
  160.         }
  161. #undef lc
  162. #undef rc
  164. }LCT;
  167. int main() {
  168. //  freopen("001.out","w",stdout);
  169.     scanf("%d%d",&n,&m) ;
  170.     for(int a,b,i=1;i<n;++i) {
  171.         scanf("%d%d",&a,&b);
  172.         Add_Edge(a,b);
  173.         Add_Edge(b,a);
  174.     }
  175.     LCT.init();
  176.     for(int opt,x,y,i=1;i<=m;++i) {
  177.         scanf("%d",&opt);
  178.         if(opt==1) scanf("%d",&x),LCT.access(x);
  179.         if(opt==2) scanf("%d%d",&x,&y),printf("%d\n",LCT.query(x,y));
  180.         else if(opt==3) scanf("%d",&x),printf("%d\n",SEG_T.query(1,1,n,ldfn[x],rdfn[x]));
  181.     }
  182.     return 0;
  183. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注