题解 CF1187E 【Tree Painting】
GIFBMP
2020-03-24 08:42:34
树形DP好题！
### 正题
我们可以发现，确定第一个点后，后面选点的顺序就不影响权值了。
所以，我们设 $g_x$ 表示先选点 $x$ 时整棵树获得的权值。
我们发现，$g_x$ 直接算比较麻烦，所以，我们定义 $f_x$ 表示选了点 $x$ 后它的**子树**对它的贡献。
易得递推式：
$$f_x=size_x+\sum_{i\in son_x}f_i$$
于是我们得出：
$$g_1=n+\sum_{\{i,1\}\in E}f_i$$
然而，怎么算其它的 $g_i$ 呢？最暴力的思想是以每个点为根重新 $dfs$，然而，这样是 $\Theta (n^2)$ 的，通过不了本题。
所以我们要使用**换根DP**。
怎么换根呢？
来看下面的图：
易得：
$$g_y=n+(n-size_y)+\sum_{i\in son_x|i\ne y}f_i+\sum_{i\in son_y}f_i$$
$$=n+(n-size_y)+\sum_{i\in son_x|i\ne y}f_i+f_y-size_y$$
$$=n+(n-size_y)+\sum_{i\in son_x}f_i-size_y$$
$$=g_x+n-2\times size_y$$
### Code:
```cpp
#include <cstdio>
#include <vector>
using namespace std ;
typedef long long ll ;
const int MAXN = 2e5 + 10 ;
int n , size[MAXN] ;
vector <int> G[MAXN] ;
ll f[MAXN] , g[MAXN] , ans ;
ll max (ll a , ll b) {
return a > b ? a : b ;
}
void dfs1 (int x , int fa) {
size[x] = 1 ;
for (int i = 0 ; i < G[x].size () ; i++) {
int v = G[x][i] ;
if (v == fa) continue ;
dfs1 (v , x) ;
size[x] += size[v] ;
f[x] += f[v] ;
}
f[x] += size[x] ;
}
void dfs2 (int x , int fa) {
if (x != 1) {
g[x] = g[fa] + n - size[x] * 2 ;
ans = max (ans , g[x]) ;
}
for (int i = 0 ; i < G[x].size () ; i++) {
int v = G[x][i] ;
if (v == fa) continue ;
dfs2 (v , x) ;
}
}
int main () {
scanf ("%d" , &n) ;
for (int i = 1 ; i < n ; i++) {
int u , v ;
scanf ("%d %d" , &u , &v) ;
G[u].push_back (v) ;
G[v].push_back (u) ;
}
dfs1 (1 , 0) ;
ans = g[1] = f[1] ;
dfs2 (1 , 0) ;
printf ("%lld" , ans) ;
return 0 ;
}
```