题解 CF1187E 【Tree Painting】

· · 题解

树形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:

#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 ;
}