w wyl123ly 的博客
MD

P3478 STA-Station

3 KB 2026.10.11 原文件

P3478 [POI2008] STA-Station

link

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

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

对于全部的测试点,保证 ,,给出的是一棵树。

思路:树形dp(换根dp)。

我们设1节点为根节点,并先统计完1节点的答案。

接下来设计状态转移方程:

我们设 为以 为根节点时,所有节点到根节点的深度之和。

设 为 节点的子节点,则可以得到状态转移方程:

其中 是指 节点的子树的大小。

是移到 节点后,除了 的子树的节点外的节点到 节点的距离增加的值。

则是移到 节点后, 的子树的所有节点到 节点距离减少的值。

则这个过程可以用两遍 来解决。

第一遍:统计以 节点为根节点时候的答案,并预处理 数组。

void predfs(int pos,int fa,int dep){
	dp[1] += dep;
	for(int to : tree[pos]){
		if(to != fa){
			predfs(to,pos,dep + 1);
			sz[pos] += sz[to];
		}
	}
}

第二遍:直接使用状态转移方程转移,注意是从根节点往子节点 。

void dfs(int pos,int fa){
	for(int to : tree[pos]){
		if(to != fa){
			dp[to] = dp[pos] + n - 2 * sz[to];
			dfs(to,pos);
		}
	}
}

最后遍历整个 数组并且输出答案即可。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
const int MAXN = 1e6 + 7;
vector<int> tree[MAXN];
int n;
int dp[MAXN];
int sz[MAXN];
void predfs(int pos,int fa,int dep){
	dp[1] += dep;
	for(int to : tree[pos]){
		if(to != fa){
			predfs(to,pos,dep + 1);
			sz[pos] += sz[to];
		}
	}
}
void dfs(int pos,int fa){
	for(int to : tree[pos]){
		if(to != fa){
			dp[to] = dp[pos] + n - 2 * sz[to];
			dfs(to,pos);
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i = 1;i < n;i++){
		int x,y;
		cin>>x>>y;
		tree[x].push_back(y);
		tree[y].push_back(x);
	}
	for(int i = 1;i <= n;i++) sz[i] = 1;
	predfs(1,0,1);
	dfs(1,0);
	int ans = 0,id = 1;
	for(int i = 1;i <= n;i++){
		if(dp[i] > ans){
			ans = dp[i],id = i;
		}
	}
	cout<<id;
	return 0;
}

复杂度 ,可以通过本题。