洛谷P3478STA-Station 题解

题目链接

题目给出一个$n$个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大。

这是一道树形DP的题,画两张图不难看出来,当一棵以$u$为根的树,变成以$v$为根的树,那么$v$子树的所有结点深度都会减少1,而不在$v$子树的所有结点深度都会增加1。

那么,我们先预处理一棵以1为根节点的树,处理出来每个结点的子树大小。用$size_v$表示以$v$为根的子树大小,不在$v$子树上的结点数量为$n-size_u$

于是有dp方程,令$dp_u$为以$u$为根结点的树的所有点深度和,当根从$u$转移到$v$时候,则

然后只要先dfs一次,预处理出$dp_1$,以及各点子树大小。然后再DP一下,就AC了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>

using LL=long long;

const int inf=0x7fffffff;

const int maxn=1e6+10;

typedef struct EdgeNode
{
int to;
EdgeNode *next;
EdgeNode(int to,EdgeNode *nxt):to(to),next(nxt){}
}*Edge;

Edge head[maxn];

inline void add_edge(int u,int v)
{
head[u]=new EdgeNode(v,head[u]);
head[v]=new EdgeNode(u,head[v]);
}

int n;
int size[maxn];
LL dp[maxn];

void dfs(int pos,int dad,int dep)
{
dp[1]+=dep;
size[pos]=1;
for(Edge node=head[pos];node;node=node->next)
{
int to=node->to;
if(to!=dad)
{
dfs(to,pos,dep+1);
size[pos]+=size[to];
}
}
}

void DP(int pos,int dad)
{
for(Edge node=head[pos];node;node=node->next)
if(node->to!=dad)
{
dp[node->to]=dp[pos]+n-2*size[node->to];
DP(node->to,pos);
}
}

int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
}
dfs(1,0,1);
LL ans=0;
int pot=1;
DP(1,0);
for(int i=1;i<=n;i++)
if(ans<dp[i])
{
ans=dp[i];
pot=i;
}
printf("%d\n",pot);
return 0;
}