树形DP优化：POI 2008 STA-Station问题解析

1. 题目背景与核心需求解析

这道题目来自波兰信息学奥林匹克竞赛（POI 2008），编号P3478，在洛谷题库中的编号是2730。题目要求我们解决一个典型的树形结构问题——在给定的树中找到最优的根节点，使得该节点作为根时所有节点的深度之和最大。

1.1 题目场景还原

想象你是一家大型企业的IT主管，需要在一个多层级办公网络中部署核心服务器。每个办公室都是一个节点，网络连接形成树状结构。你需要找到一个最佳位置放置主服务器，使得所有办公室访问它的总"跳数"最大（实际应用中可能是为了压力测试或负载均衡模拟）。这就是STA-Station问题的现实映射。

1.2 数学建模

给定一棵n个节点的无根树，设depth[u]表示节点u的深度（根节点深度为0）。我们需要找到一个根节点r，使得Σdepth[i] (i=1~n)最大。直接解法是对每个节点作为根计算一次深度和，但O(n²)复杂度在n≤1e6时会超时。

2. 高效算法设计与证明

2.1 树形DP的两次扫描法

这个问题的标准解法是使用树形动态规划结合二次扫描技术。核心思想是：

1. 第一次后序遍历计算以任意节点（如1号）为根时的子树大小和初始深度和
2. 第二次前序遍历通过父节点信息推导相邻节点的深度和

cpp复制void dfs1(int u, int fa) {
    size[u] = 1;
    for(int v : tree[u]) {
        if(v == fa) continue;
        dfs1(v, u);
        size[u] += size[v];
        sum[u] += sum[v] + size[v];
    }
}

void dfs2(int u, int fa) {
    for(int v : tree[u]) {
        if(v == fa) continue;
        sum[v] = sum[u] + n - 2 * size[v];
        dfs2(v, u);
    }
}

2.2 复杂度分析

两次DFS遍历均访问每个节点恰好一次，每次处理时间为O(degree(u))，根据握手定理Σdegree(u)=2(n-1)，因此总