题解 P5773 【[JSOI2016]轻重路径】
zsq259
·
·
题解
题解 JSOI2013 轻重路径
题面
luogu
解析
设根节点为 rt.
一个点 x 会由重儿子变为轻儿子的一个必要条件是 size_{x}\leq \frac{size_{rt}}{2}.
于是考虑二分找到满足上面条件的 $size$ 最大的 $x$,判断它是否会变为轻儿子,另外如果它是被删掉的要特判.
然后将 $rt$ 设为 $x$,继续按上面的搞.
这样的操作不会超过 $log_{n}$ 次,因为每次 $size_{rt}$ 都会至少除以 $2$.
### code
```cpp
#include <iostream>
#include <stdio.h>
#include <cstring>
#define ll long long
#define filein(a) freopen(a,"r",stdin)
#define fileout(a) freopen(a,"w",stdout);
using namespace std;
inline int read(){
int sum=0,f=1;char c=getchar();
while((c<'0'||c>'9')&&c!=EOF){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'&&c!=EOF){sum=sum*10+c-'0';c=getchar();}
return sum*f;
}
const int N=2000005;
struct node{int s[2],sz,top,dep,fa,son,id;}a[N];
int n,t[N];ll sum;
int pla[N],tot;
inline void change(int x,int y){for(;x<=n;x+=x&-x) t[x]+=y;}
inline int query(int x){int y=0;for(;x;x-=x&-x) y+=t[x];return y;}
inline void dfs1(int x,int fa){
a[x].fa=fa;a[x].dep=a[fa].dep+1;
a[x].sz=1;
for(int i=0;i<=1;i++){
int k=a[x].s[i];
if(!k) continue;
dfs1(k,x);a[x].sz+=a[k].sz;
if(a[k].sz>a[a[x].son].sz) a[x].son=k;
}
}
inline void dfs2(int x,int top){
a[x].top=top;pla[a[x].id=++tot]=x;
if(!a[x].son) return ;
dfs2(a[x].son,top);
for(int i=0;i<=1;i++){
int k=a[x].s[i];
if(k&&k!=a[x].son) dfs2(k,k);
}
}
inline int get(int x){
if(!x) return 0;
return query(a[x].id+a[x].sz-1)-query(a[x].id-1);
}
inline int find(int x,int d){
while(a[a[x].top].dep>d) x=a[a[x].top].fa;
return pla[a[x].id-(a[x].dep-d)];
}
inline int side(int x){return x==a[a[x].fa].s[1];}
int main(){
n=read();
for(int i=1;i<=n;i++)
a[i].s[0]=read(),a[i].s[1]=read();
dfs1(1,0);dfs2(1,1);
for(int i=1;i<=n;i++) sum+=a[i].son;
for(int i=1;i<=n;i++) change(i,1);
printf("%lld\n",sum);
int Q=read();
while(Q--){
int x=read(),rt=1;change(a[x].id,-1);
while(1){
int l=a[rt].dep+1,r=a[x].dep,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(get(find(x,mid))<=get(rt)/2) ans=mid,r=mid-1;
else l=mid+1;
}
if(!ans) break;
int x1=find(x,ans),x2=a[a[x1].fa].s[side(x1)^1];
if(a[a[x1].fa].son==x1){
if(get(x1)+1==get(x2)) sum+=x2-x1,a[a[x1].fa].son=x2;
else if(!get(x1)&&!(get(x2))) sum-=x1,a[a[x1].fa].son=0;
}
rt=x1;
}
printf("%lld\n",sum);
}
return 0;
}
```