51nod 1576 Tree and permutation（树的重心+dfn序）

乍一看我不会。

先不考虑加点。

先考虑没有那个除\(2\)。

考虑每一条边的贡献，假设某一条边把这棵树分成大小为x,y的两个部分。

那么这条边最多可以被使用\(min(x,y)*2\)次（因为有进有出），即贡献最大为\(min(x,y)*2*\)这条边的权值。

那么能不能让每一条边的被使用达到最大呢？

显然可以。

那怎么快速算这个东西呢？不可能每加一个点就dfs一遍吧。那样就\(T\)飞了。

实际上这个东西就是每个点到树的重心的距离\(*2\)。

为什么？因为满足以树的重心为根每一个子树大小\(<\)总共的节点数。每一棵子树内所有点都要向子树外也就是根（重心）连边。

然后发现这个除\(2\)没有向下取整。

所以就是求所有的点到重心的距离和。

然后加点的话可以离线然后\(dfn序\)维护一下。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

#define ls now<<1

#define rs now<<1|1

const int N=101000;

int cnt,head[N];

struct edge{

	int to,nxt;

}e[N*2];

void add_edge(int u,int v){

	cnt++;

	e[cnt].nxt=head[u];

	e[cnt].to=v;

	head[u]=cnt;

}

int size[N],fa[N][22],dep[N],dfn[N],tot;

void dfs(int u,int f){

	size[u]=1;

	dfn[u]=++tot;

	fa[u][0]=f;dep[u]=dep[f]+1;

	for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];

	int maxson=-1;

	for(int i=head[u];i;i=e[i].nxt){

		int v=e[i].to;

		if(v==f)continue;

		dfs(v,u);

		size[u]+=size[v];

	}

}

int getlca(int x,int y){

	if(dep[x]<dep[y])swap(x,y);

	for(int i=20;i>=0;i--)

		if(dep[fa[x][i]]>=dep[y])x=fa[x][i];

	if(x==y)return x;

	for(int i=20;i>=0;i--)

		if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

	return fa[x][0];

}

int sum[N*4];

void update(int now){

	sum[now]=sum[ls]+sum[rs];

}

void build(int l,int r,int now){

	if(l==r){

		if(l==1)sum[l]=1;

		return ;

	}

	int mid=(l+r)>>1;

	build(l,mid,ls);

	build(mid+1,r,rs);

	update(now);

}

void add(int l,int r,int x,int now){

	if(l==r){

		sum[now]=1;

		return;

	}

	int mid=(l+r)>>1;

	if(x>mid)add(mid+1,r,x,rs);

	else add(l,mid,x,ls);

	update(now);

}

int check(int l,int r,int L,int R,int now){

	if(l==L&&r==R)return sum[now];

	int mid=(l+r)>>1;

	if(L>mid)return check(mid+1,r,L,R,rs);

	else if(R<=mid)return check(l,mid,L,R,ls);

	else return check(l,mid,L,mid,ls)+check(mid+1,r,mid+1,R,rs);

}

int up(int x,int y){

	for(int i=20;i>=0;i--)

		if(dep[fa[x][i]]>dep[y])x=fa[x][i];

	return x;

}

int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return sum*f;

}

int n,root;

long long ans;

int main(){

	n=read();n++;

	root=1;ans=0;

	for(int i=2;i<=n;i++){

		int v=read();

		add_edge(i,v);add_edge(v,i);

	}

	dfs(1,0);

	build(1,n,1);

	for(int i=2;i<=n;i++){

		add(1,n,dfn[i],1);

		int lca=getlca(root,i);

		ans+=(long long)(dep[root]+dep[i]-2ll*dep[lca]);

		if(lca==root){

			int x=up(i,root);

			int sizex=check(1,n,dfn[x],dfn[x]+size[x]-1,1);

			if(sizex>i-sizex)root=x,ans+=(long long)(i-sizex*2ll);

		}

		else{

			int x=fa[root][0];

			int sizex=check(1,n,dfn[root],dfn[root]+size[root]-1,1);

			if(i-sizex>sizex)root=x,ans+=(long long)(sizex*2ll-i);

		}

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

51nod 1576 Tree and permutation（树的重心+dfn序）

最新文章

热门文章