题目描述

难度分:$2100$

输入$n(2 \leq n \leq 2 \times 10^5)$表示一棵有$n$个节点的无向无根树，然后输入这棵树的$n-1$ 条边（节点编号从$1$开始）。

一开始，所有节点都是白色的。第一回合，你可以随便选一个节点，并把它涂成黑色，得到$n$分。

在接下来的$n-1$个回合中，每回合，选择一个与黑色节点相邻的白色节点。设该白色节点所在的白色连通块的大小为$k$，你会先得到$k$分，然后把该白色节点涂成黑色。

输出最大得分和。

输入样例$1$

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

输出样例$1$

36

输入样例$2$

5
1 2
1 3
2 4
2 5

输出样例$2$

14

算法

换根DP

注意到第一个染色的节点$u$可以任意，染完它之后，其实整张图就被节点$u$分裂开来了，其他连通块都是这个节点的子树。接下来要染节点$u$相邻的节点$v$，也就是$u$为根时的子节点。

进一步的，如果确定一个根，就能够得到一个得分和。不断更换第一个节点就能得到不同的得分和，因此我们的目的就是不断换根，获得最大的得分和，这样就很容易想到换根树形DP了。先随便确定一个根，假设是$1$。

第一次$DFS$

状态定义

$f[u]$表示将$u$为根的子树全部染黑的最大和，在这个定义下，把根为$1$的树染黑答案就是$f[1]$。

状态转移

可以通过染色过程发现，要染$u$为根的子树，第一步染根节点就能得$cnt[u]$分（$cnt[u]$是在$1$为整棵树的根的情况下，子树$u$的节点数目）。接下来要染$u$的子树，就有状态转移方程$f[u]=cnt[u]+\Sigma_{v}f[v]$，其中$v$是$u$的子节点（在$1$为整棵树根的意义下）。

第二次$DFS$

这样经过一次$DFS$，我们可以得到一个初始的答案$ans=f[1]$，接下来开始换根。定义递归函数$dfs(u,vx)$，$vx$是$u$上面所有节点对它的贡献，当$f[u]+vx$比当前答案大时就可以更新答案。再遍历$u$的子节点$v$时进行状态转移，对于节点$v$，我们要计算出它的$vx’=vx+\Delta$，才能进行下一层的递归$dfs(v,vx’)$，也就是要算出$vx$的增量$\Delta$。

首先要加上$v$上面所有节点的数量$n-cnt[v]$，然后把$f[v]+cnt[v]$从$f[u]$中挖掉，这样才能刨去子树$v$对$u$的影响，因此$\Delta=f[u]-f[v]-cnt[v]+n-cnt[v]$。

复杂度分析

时间复杂度

两次$DFS$，时间复杂度是$O(n)$的（节点数和边数都是$O(n)$规模），因此算法的时间复杂度为$O(n)$。

空间复杂度

递归在最差情况下树退化成链要$n$层，空间复杂度为$O(n)$。树用邻接表来存，空间复杂度也是$O(n)$。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;

const int N = 200010;
int n, u, v, cnt[N];
vector<int> graph[N];
LL ans, f[N];

LL dfs1(int u, int fa) {
    cnt[u] = 1;
    f[u] = 0;
    for(int v: graph[u]) {
        if(v == fa) continue;
        f[u] += dfs1(v, u);
        cnt[u] += cnt[v];
    }
    f[u] += cnt[u];
    return f[u];
}

void dfs2(int u, int fa, LL vx) {
    if(f[u] + vx > ans) {
        ans = f[u] + vx;
    }
    for(int v: graph[u]) {
        if(v == fa) continue;
        dfs2(v, u, vx + f[u] - f[v] - cnt[v] + n - cnt[v]);
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        graph[i].clear();
    }
    for(int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    ans = dfs1(1, 0);     // 初始答案
    dfs2(1, 0, 0);
    printf("%lld\n", ans);
    return 0;
}