A47446.[CSP-S2019]题解

from：soar_ing 创建时间：2019-11-18 16:46
两次dfs和一次倍增

二叉树:

深度较浅,暴力换重儿子

对于一个点,若x不是重心,重心要么在重儿子子树里,要么在父亲节点上

第一次dfs求出son[x],s[x]

p[x][i]表示x沿着重儿子走2
i
步

第二次dfs换根,把上面数组的定义从以1为根改为以x为根

对于一条边,以下方的重心,可以直接倍增,可以跳的条件为上方

的size<=sum/2

对于上方的重心,换根时记录信息,倍增方法一样

#include<bits/stdc++.h>
#define o 300005
#define g0(a) memset(a,0,sizeof(a))
#define gc(a,b) memcpy(a,b,sizeof(a))
using namespace std;
inline int read()
{
	register int data=0,w=1;
	char ch=0;
	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch=='-')w=-1,ch=getchar();
	while(ch>='0'&&ch<='9')data=(data<<1)+(data<<3)+(ch^48),ch=getchar();
	return data*w;
}
struct node
{
	int to,next;
}w[o*2];
int n,T,son[o],s[o],pr[o],son2[o],p[o][18],son3[o],f[o],h[o],cnt,s2[o];
void add(int x,int y){++cnt;w[cnt].to=y;w[cnt].next=h[x];h[x]=cnt;}
void dfs(int x,int fa)
{
	s[x]=1;pr[x]=fa;
	for(int i=h[x];i;i=w[i].next)
	{
		int y=w[i].to;
		if(y==fa)continue;
		dfs(y,x);s[x]+=s[y];
		if(s[y]>s[son[x]])son2[x]=son[x],son[x]=y;
		else if(s[y]>s[son2[x]])son2[x]=y;
	}
	p[x][0]=son[x];
	for(int i=1;i<=17;i++)p[x][i]=p[p[x][i-1]][i-1];
}
long long ans;
int judge(int x,int sum)
{
	return x*(max(s2[son3[x]],sum-s2[x])<=sum/2);
}
void dfs2(int x,int fa)
{
	for(int i=h[x];i;i=w[i].next)
	{
		int y=w[i].to;
		if(y==fa)continue;
		s2[x]=s[1]-s[y];f[y]=0;f[x]=0;
		if(son[x]==y)son3[x]=son2[x];
		else son3[x]=son[x];
		if(s2[fa]>s2[son3[x]])son3[x]=fa;
		p[x][0]=son3[x];
		for(int j=1;j<=17;j++)p[x][j]=p[p[x][j-1]][j-1];
		int b=x;
		for(int j=17;j>=0;j--)if(s2[x]-s2[p[b][j]]<=s2[x]/2)b=p[b][j];
		ans+=judge(son3[b],s2[x])+judge(b,s2[x])+judge(f[b],s2[x]);
		b=y;
		for(int j=17;j>=0;j--)if(s2[y]-s2[p[b][j]]<=s2[y]/2)b=p[b][j];
		ans+=judge(son3[b],s2[y])+judge(b,s2[y])+judge(f[b],s2[y]);
		f[x]=y;
		dfs2(y,x);
	}
	son3[x]=p[x][0]=son[x];f[x]=pr[x];
	for(int j=1;j<=17;j++)p[x][j]=p[p[x][j-1]][j-1];
	s2[x]=s[x];
}
int main()
{
	T=read();
	while(T--)
	{
		g0(h);g0(son);g0(f);g0(pr);cnt=0;ans=0;
		n=read();
		for(int i=1;i<n;i++)
		{
			int x=read(),y=read();
			add(x,y);add(y,x);
		}
		dfs(1,0);
		gc(s2,s);gc(son3,son);gc(f,pr);
		dfs2(1,0);
		cout<<ans<<'\n';
	}
	return 0;
}