自动搬运

查看原文

来自洛谷，原作者为

	zsq259 这个家伙很懒，什么也没有留下................................................

搬运于2025-08-24 22:14:15，当前版本为作者最后更新于2020-03-01 21:08:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解 JSOI2013 轻重路径

题面

luogu

解析

设根节点为 $rt$.

一个点 $x$ 会由重儿子变为轻儿子的一个必要条件是 $size_{x}\leq \frac{size_{rt}}{2}$.

$size[x]$ 表示 $x$ 当前的子树大小,这个可以用树状数组维护.

于是考虑二分找到满足上面条件的 $size$ 最大的 $x$,判断它是否会变为轻儿子,另外如果它是被删掉的要特判.

然后将 $rt$ 设为 $x$,继续按上面的搞.

这样的操作不会超过 $log_{n}$ 次,因为每次 $size_{rt}$ 都会至少除以 $2$.

code

#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;
}