[POI2008] STA-Station

题目描述

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

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

输入格式

第一行有一个整数，表示树的结点个数 $n$。
接下来 $(n - 1)$ 行，每行两个整数 $u, v$，表示存在一条连接 $u, v$ 的边。

输出格式

本题存在 Special Judge。

输出一行一个整数表示你选择的结点编号。如果有多个结点符合要求，输出任意一个即可。

样例 #1

样例输入 #1

样例输出 #1

提示

样例 1 解释

输出 $7$ 和 $8$ 都是正确答案。

数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 10^6$，$1 \leq u, v \leq n$，给出的是一棵树。

题解

这是一道树型 DP 的题目。我们可以使用 DFS 来遍历整棵树，计算每个节点的子树大小和深度。具体来说，我们可以使用两个数组 $siz$ 和 $dep$ 分别存储每个节点的子树大小和深度。

之后我们考虑如何由父节点的答案得出子节点的答案，不难发现有以下式子：

$$f[i] = f[father] + n - 2 \times size[i]$$

这样我们就可以先计算出根节点的所有深度之和，然后$O(1)$的扩展到子节点了。

具体实现细节可以参考下面的代码。

代码实现

本来想着用java写的，但是这题java爆栈了，这里放一下C++的代码

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 2000005;

vector<int> edge[MAXN];
int n, siz[MAXN], dep[MAXN];
long long f[MAXN];

// 计算每个节点的子树大小
int dfs(int x, int fa)
{
    dep[x] = dep[fa] + 1; // 计算当前节点的深度
    int ans = 1; // 初始化子树大小为 1
    for (int i : edge[x]) // 遍历当前节点的邻居节点
    {
        if (i != fa) // 如果邻居节点不是当前节点的父节点
            ans += dfs(i, x); // 递归计算邻居节点的子树大小，并将结果加到当前节点的子树大小中
    }
    return siz[x] = ans; // 将当前节点的子树大小存储到 siz 数组中，并返回结果
}

// 计算以 x 为根节点的子树中，价值最大的节点的编号
int dp(int x, int fa)
{
    int ans = x; // 初始化答案为当前节点的编号
    for (int i : edge[x]) // 遍历当前节点的邻居节点
    {
        if (i != fa) // 如果邻居节点不是当前节点的父节点
        {
            f[i] = f[x] + n - siz[i] - siz[i]; // 计算邻居节点的答案
            int temp = dp(i, x); // 递归计算邻居节点的答案
            if (f[temp] > f[ans]) // 如果邻居节点的答案比当前节点的答案更大
                ans = temp; // 更新答案为邻居节点的编号
        }
    }
    return ans; // 返回以 x 为根节点的子树中，价值最大的节点的编号
}

int main()
{
    cin >> n;
    for (int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dep[0] = -1; // 初始化根节点的深度为 -1
    dfs(1, 0); // 计算每个节点的子树大小
    for (int i = 1; i <= n; i++)
        f[1] += dep[i]; // 计算以 1 为根节点的子树中，每个节点的深度之和
    int ans = dp(1, 0); // 计算以 1 为根节点的子树中，价值最大的节点的编号
    cout << ans << endl; // 输出结果
    return 0;
}

时间复杂度

本题的时间复杂度为 $O(n)$，其中 $n$ 表示树的节点数

洛谷P3478 [POI2008] STA-Station 题解