[spojQTREE6]Query on a tree VI

考虑如下构造：

新建一条边$(0,1)$，并将原树以0为根建树，记$fa_{x}$为$x$的父亲（其中$1\le x\le n$）

维护两棵森林，分别记作$T_{0/1}$，每一条边恰属于一棵，其中$(x,fa_{x})\in T_{0}$当且仅当$x$为白色点

此时，考虑节点$x$的答案（不妨假设$x$为白色点），即是$T_{0}$去掉$x$所在连通块根节点（深度最小的节点）后所在连通块子树大小，正确性显然

对这两棵森林使用LCT维护，考虑修改和查询：

1.修改时，即增加并删除一条边

2.查询时，不妨假设$x$为白色，将$T_{0}$中$x$所在连通块内深度最小的点make_root后，不难发现即求该点右儿子子树范围内的点数，显然容易维护（"子树范围"定义以及如何维护见QTREE5）

考虑如何快速找到该点，考虑保持树的形态（注意初始状态），即在make_root时不rev，那么find_root的结果即为该最浅的点

这样在加边和删边时并不会产生影响（其实通常的LCT在加边和删边时也并不需要rev），查询时的做法上面已经给出，即find_root一下即可

时间复杂度为$o(n\log n)$，可以通过

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 100005

  4 vector<int>v[N];

  5 int n,m,x,y,f[N],col[N];

  6 struct LCT{

  7     int fa[N],vir[N],sz[N],ch[N][2];

  8     LCT(){

  9         for(int i=1;i<N;i++)sz[i]=1;

 10     }

 11     bool check(int k){

 12         return ((ch[fa[k]][0]!=k)&&(ch[fa[k]][1]!=k));

 13     }

 14     int which(int k){

 15         return ch[fa[k]][1]==k;

 16     }

 17     void up(int k){

 18         sz[k]=sz[ch[k][0]]+sz[ch[k][1]]+vir[k]+1;

 19     }

 20     void add_vir(int k){

 21         vir[fa[k]]+=sz[k];

 22     }

 23     void del_vir(int k){

 24         vir[fa[k]]-=sz[k];

 25     }

 26     void rotate(int k){

 27         int f=fa[k],g=fa[f],p=which(k);

 28         fa[k]=g;

 29         if (!check(f))ch[g][which(f)]=k;

 30         fa[ch[k][p^1]]=f,ch[f][p]=ch[k][p^1];

 31         fa[f]=k,ch[k][p^1]=f;

 32         up(f),up(k);

 33     }

 34     void splay(int k){

 35         for(int i=fa[k];!check(k);i=fa[k]){

 36             if (!check(i)){

 37                 if (which(i)==which(k))rotate(i);

 38                 else rotate(k);

 39             }

 40             rotate(k);

 41         }

 42     }

 43     void access(int k){

 44         int lst=0;

 45         while (k){

 46             splay(k);

 47             if (ch[k][1])add_vir(ch[k][1]);

 48             if (lst)del_vir(lst);

 49             ch[k][1]=lst,up(k);

 50             lst=k,k=fa[k];

 51         }

 52     }

 53     void make_root(int k){

 54         access(k);

 55         splay(k);

 56     }

 57     int find_root(int k){

 58         access(k);

 59         splay(k);

 60         while (ch[k][0])k=ch[k][0];

 61         splay(k);

 62         return k;

 63     }

 64     void add(int x,int y){

 65         make_root(x);

 66         make_root(y);

 67         fa[y]=x,add_vir(y),up(x);

 68     }

 69     void del(int x,int y){

 70         make_root(x);

 71         access(y);

 72         fa[y]=ch[x][1]=0,up(x);

 73     }

 74     int query(int k){

 75         k=find_root(k);

 76         return sz[ch[k][1]];

 77     }

 78 }T[2];

 79 void dfs(int k,int fa){

 80     f[k]=fa;

 81     for(int i=0;i<v[k].size();i++)

 82         if (v[k][i]!=fa)dfs(v[k][i],k);

 83 }

 84 int main(){

 85     scanf("%d",&n);

 86     for(int i=1;i<n;i++){

 87         scanf("%d%d",&x,&y);

 88         v[x].push_back(y);

 89         v[y].push_back(x);

 90     }

 91     dfs(1,n+1);

 92     for(int i=1;i<=n;i++){

 93         col[i]=1;

 94         T[1].add(f[i],i);

 95     }

 96     scanf("%d",&m);

 97     for(int i=1;i<=m;i++){

 98         scanf("%d%d",&x,&y);

 99         if (!x)printf("%d\n",T[col[y]].query(y));

100         else{

101             T[col[y]].del(f[y],y);

102             col[y]^=1;

103             T[col[y]].add(f[y],y);

104         }

105     }

106     return 0;

107 }

巴特西

[spojQTREE6]Query on a tree VI

最新文章

热门文章