[loj3329]有根树

题目即求$\min_{C}\max(|C|,\min_{x\notin C}w_{x})$，考虑将$w$从大到小排序，即为$\min_{1\le k\le n}\max(k,w_{k+1})$

考虑若$k<w_{k+1}$，那么让$k$加1一定不劣，因此必然有一个最优的$k$满足$k\ge w_{k+1}$，同时若满足这个条件再让$k$增加一定劣，所以题目即求最小的$k$满足$k\ge w_{k+1}$

考虑对于$w$执行插入操作后为$w'$（从大到小排序），那么必然有$w_{k}\le w'_{k}\le \max(w_{k-1},w_{k}+1)$，证明略

根据这个结论可以发现：如果上一次的答案$k$仍满足$k\ge w'_{k+1}$，那么答案不变；如果$k<w'_{k+1}$，那么答案为$k+1$

（删除操作类似，有$\min(w_{k+1},w_{k}-1)\le w'_{k}\le w_{k}$，因此答案只可能为$k$或$k-1$）

考虑如何维护这个过程，用树链剖分+线段树来维护子树大小（注意未插入的子树需特殊处理），维护区间的在前$k$大中的$min$和不在前$k$大中的$max$（值相同任意）

具体维护时，可以在$o(1)$的范围内修改$k$来简化操作，这样的复杂度仍然可以保证，同时区间$\pm 1$的操作由于链上子树大小单调递增，因此至多存在一个修改后改变是否为前$k$大状态的点，暴力修改即可

其实复杂度还可以优化到$o(n\log n)$，因为复杂度的瓶颈在于链修改，链修改+单点查询可以改为单点修改+子树查询，用dfs序即可维护

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

  2 using namespace std;

  3 #define N 500005

  4 #define eps (N<<2)

  5 #define oo 0x3f3f3f3f

  6 #define L (k<<1)

  7 #define R (L+1)

  8 #define mid (l+r>>1)

  9 struct ji{

 10     int nex,to;

 11 }edge[N<<1];

 12 int E,n,q,x,y,s,ans,head[N],sz[N],fa[N],son[N],id[N],top[N],mx[N<<2],mn[N<<2],f[N<<2];

 13 void add(int x,int y){

 14     edge[E].nex=head[x];

 15     edge[E].to=y;

 16     head[x]=E++;

 17 }

 18 void dfs1(int k,int f){

 19     sz[k]=1;

 20     fa[k]=f;

 21     for(int i=head[k];i!=-1;i=edge[i].nex)

 22         if (edge[i].to!=f){

 23             dfs1(edge[i].to,k);

 24             sz[k]+=sz[edge[i].to];

 25             if (sz[edge[i].to]>sz[son[k]])son[k]=edge[i].to;

 26         }

 27 }

 28 void dfs2(int k,int t){

 29     id[k]=++x;

 30     top[k]=t;

 31     if (son[k])dfs2(son[k],t);

 32     for(int i=head[k];i!=-1;i=edge[i].nex)

 33         if ((edge[i].to!=fa[k])&&(edge[i].to!=son[k]))dfs2(edge[i].to,edge[i].to);

 34 }

 35 void upd(int k,int x){

 36     f[k]+=x;

 37     mx[k]+=x;

 38     mn[k]+=x;

 39 }

 40 void up(int k){

 41     mx[k]=max(mx[L],mx[R])+f[k];

 42     mn[k]=min(mn[L],mn[R])+f[k];

 43 }

 44 void down(int k){

 45     upd(L,f[k]);

 46     upd(R,f[k]);

 47     f[k]=0;

 48 }

 49 void del_mx(int k,int l,int r){

 50     if (l==r){

 51         mn[k]=f[k];

 52         mx[k]=-oo;

 53         return;

 54     }

 55     down(k);

 56     if (mx[k]==mx[L])del_mx(L,l,mid);

 57     else del_mx(R,mid+1,r);

 58     up(k);

 59 }

 60 void del_mn(int k,int l,int r){

 61     if (l==r){

 62         mx[k]=f[k];

 63         mn[k]=oo;

 64         return;

 65     }

 66     down(k);

 67     if (mn[k]==mn[L])del_mn(L,l,mid);

 68     else del_mn(R,mid+1,r);

 69     up(k);

 70 }

 71 void add(int k,int l,int r,int x,int y){

 72     if (l==r){

 73         if ((y)&&(mn[1]<f[k]))ans++;

 74         if ((!y)&&(abs(mn[k]-oo)>eps))ans--;

 75         mx[k]=-oo;

 76         mn[k]=oo;

 77         if ((y)&&(f[k]<=mn[1]))mx[k]=f[k];

 78         if ((y)&&(f[k]>mn[1]))mn[k]=f[k];

 79         return;

 80     }

 81     down(k);

 82     if (x<=mid)add(L,l,mid,x,y);

 83     else add(R,mid+1,r,x,y);

 84     up(k);

 85 }

 86 void update(int k,int l,int r,int x,int y,int z){

 87     if ((l>y)||(x>r))return;

 88     if ((x<=l)&&(r<=y)){

 89         if ((z>0)&&(mx[k]==mn[1])){

 90             ans++;

 91             del_mx(k,l,r);

 92         }

 93         if ((z<0)&&(mn[k]==mn[1])&&(abs(mn[k]-oo)>eps)){

 94             ans--;

 95             del_mn(k,l,r);

 96         }

 97         upd(k,z);

 98         return;

 99     }

100     down(k);

101     update(L,l,mid,x,y,z);

102     update(R,mid+1,r,x,y,z);

103     up(k);

104 }

105 void update(int k,int x){

106     while (k){

107         update(1,1,n,id[top[k]],id[k],x);

108         k=fa[top[k]];

109     }

110 }

111 void inc(){

112     ans++;

113     del_mx(1,1,n);

114 }

115 void dec(){

116     ans--;

117     del_mn(1,1,n);

118 }

119 int main(){

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

121     memset(head,-1,sizeof(head));

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

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

124         add(x,y);

125         add(y,x);

126     }

127     x=0;

128     dfs1(1,0);

129     dfs2(1,1);

130     memset(mx,-0x3f,sizeof(mx));

131     memset(mn,0x3f,sizeof(mn));

132     scanf("%d",&q);

133     for(int i=1;i<=q;i++){

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

135         x=2-x;

136         add(1,1,n,id[y],x);

137         update(y,2*x-1);

138         while (ans<mx[1])inc();

139         while (ans-1>=mn[1])dec();

140         printf("%d\n",ans);

141     }

142 }

巴特西

[loj3329]有根树

最新文章

热门文章