洛谷P3478 [POI2008] STA-Station 题解

发布于 2023-07-12  186 次阅读


[POI2008] STA-Station

题目描述

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

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

输入格式

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

输出格式

本题存在 Special Judge

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

样例 #1

样例输入 #1

8
1 4
5 6
4 5
6 7
6 8
2 4
3 4

样例输出 #1

7

提示

样例 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$ 表示树的节点数

end