description

analysis

需要知道一棵树的重心一定在从根出发的重链上，可以考虑先进行树链剖分弄出重儿子和次重儿子，再倍增维护重儿子
由于重链上有一个或两个重心，接下来求的重心都是深度较大的，只需判断其父节点是否也满足重心的性质即可
现在要断掉一条边\((x,y)\)，假设\(x\)是\(y\)的父亲，需要分别求出\(y\)的子树的重心、以及除了\(y\)的子树以外的树的重心
倍增数组已经维护好了所以\(y\)的重心很好求，对于视作\(x\)为根的子树则需要重新维护一次倍增数组
若\(y\)是重儿子则用次重儿子与\(x\)父亲\(size\)比较，否则用原来的重儿子比；知道了重儿子则可以重新算倍增数组
然后把\(x\)设为\(y\)的儿子，其实就是换根操作，递归下去求解，回溯时重新再算\(x\)的倍增数组；时间复杂度\(O(n\log n)\)

code

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<math.h>

#define MAXN 300005

#define MAXM MAXN*2

#define ll long long

#define reg register ll

#define fo(i,a,b) for (reg i=a;i<=b;++i)

#define fd(i,a,b) for (reg i=a;i>=b;--i)

#define rep(i,a) for (reg i=las[a];i;i=nex[i])

using namespace std;

ll las[MAXM],nex[MAXM],tov[MAXM];

ll fa[MAXN],size[MAXN],tsize[MAXN],hson[MAXN],secson[MAXN];

ll son[MAXN][20];

ll n,T,tot,ans,log2n;

inline ll read()

{

	ll x=0,f=1;char ch=getchar();

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

	while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*f;

}

inline ll max(ll x,ll y){return x>y?x:y;}

inline ll min(ll x,ll y){return x<y?x:y;}

inline void link(ll x,ll y){nex[++tot]=las[x],las[x]=tot,tov[tot]=y;}

inline void dfs1(ll x,ll y)

{

	size[x]=1,fa[x]=y;

	rep(i,x)if (tov[i]!=y)

	{

		dfs1(tov[i],x),size[x]+=size[tov[i]];

		if (size[tov[i]]>size[hson[x]])secson[x]=hson[x],hson[x]=tov[i];

		else if (size[tov[i]]>size[secson[x]])secson[x]=tov[i];

	}

	tsize[x]=size[x],son[x][0]=hson[x];

}

inline void dfs2(ll x,ll y)

{

	rep(i,x)if (tov[i]!=y)

	{

		if (tov[i]==hson[x])son[x][0]=secson[x];

		else son[x][0]=hson[x];

		if (size[y]>size[son[x][0]])son[x][0]=y;

		fo(k,1,log2n)son[x][k]=son[son[x][k-1]][k-1];

		size[x]=n-tsize[tov[i]],size[tov[i]]=tsize[tov[i]],fa[x]=fa[tov[i]]=0;

		ll now=x;

		fd(k,log2n,0)if (son[now][k] && size[x]-size[son[now][k]]<=size[x]/2)now=son[now][k];

		if (max(size[son[now][0]],size[x]-size[now])<=size[x]/2)ans+=now;

		if (max(size[son[fa[now]][0]],size[x]-size[fa[now]])<=size[x]/2)ans+=fa[now];

		now=tov[i];

		fd(k,log2n,0)if (son[now][k] && size[tov[i]]-size[son[now][k]]<=size[tov[i]]/2)now=son[now][k];

		if (max(size[son[now][0]],size[tov[i]]-size[now])<=size[tov[i]]/2)ans+=now;

		if (max(size[son[fa[now]][0]],size[tov[i]]-size[fa[now]])<=size[tov[i]]/2)ans+=fa[now];

		fa[x]=tov[i],dfs2(tov[i],x);

	}

	fa[x]=y,son[x][0]=hson[x],size[x]=tsize[x];

	fo(k,1,log2n)son[x][k]=son[son[x][k-1]][k-1];

}

int main()

{

	T=read();

	while (T--)

	{

		memset(las,0,sizeof(las)),memset(nex,0,sizeof(nex));

		memset(tov,0,sizeof(tov)),memset(secson,0,sizeof(secson));

		memset(fa,0,sizeof(fa)),memset(son,0,sizeof(son)),memset(hson,0,sizeof(hson));

		n=read(),log2n=(ll)log2(n),ans=tot=0;

		fo(i,1,n-1){ll x=read(),y=read();link(x,y),link(y,x);}

		dfs1(1,0);

		fo(j,1,log2n)fo(i,1,n)son[i][j]=son[son[i][j-1]][j-1];

		dfs2(1,0),printf("%lld\n",ans);

	}

	return 0;

}

巴特西

【JZOJ6435】【luoguP5666】【CSP-S2019】树的重心

description

analysis

code

最新文章

热门文章