P3478题解

DDream白日梦 / 2023-08-16 / 原文

P3478题解

题目描述

给定一个 \(n\) 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。

一个结点的深度之定义为该节点到根的简单路径上边的数量。

题解

本题为换根dp的模板题。

我们令 \(dp[x]\) 为以 \(x\) 为根节点的子树内的节点深度之和。令 \(s[x]\) 为以 \(x\) 为根节点的子树大小。注意：这里的深度是从节点到根的路径长，为方便求解可以考虑给0号节点设上-1。

初始时我们令根为1，换根时，注意一下更新顺序，分别更新 \(dp\) 和 \(x\) 即可。最后严谨起见，防止如下hack：

in:

ans:

我们给初始值附上1。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+100;
int n,u,v,ans,mx,dp[N],s[N],d[N];
vector<int>edge[N];
void dfs1(int x,int fa)
{
	d[x]=d[fa]+1;
	dp[x]=d[x];
	s[x]=1;
	for(int i=0;i<edge[x].size();i++)
	{
		int to=edge[x][i];
		if(to==fa)
		continue;
		dfs1(to,x);
		s[x]+=s[to];
		dp[x]+=dp[to];
	}
	return;
}
void dfs2(int x,int fa)
{
	for(int i=0;i<edge[x].size();i++)
	{
		int to=edge[x][i];
		if(to==fa)
		continue;
		int x1=dp[x],x2=dp[to],x3=s[x],x4=s[to];
		s[x]-=s[to];
		dp[x]-=dp[to]-s[x];
		dp[to]+=dp[x]-s[to];
		s[to]+=s[x];
		if(dp[to]>mx)
		{
			mx=dp[to];
			ans=to;
		}
		dfs2(to,x);
		dp[x]=x1,dp[to]=x2,s[x]=x3,s[to]=x4;
	}
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	d[0]=-1;
	dfs1(1,0);
	mx=dp[1];
	ans=1;
	dfs2(1,0);
	cout<<ans;
	return 0;
}