CF1187E Tree Painting

Bertha 。 2021-12-10 17:49 209阅读 0赞

**思路：**

树形dp，首先使用dp计算以1为根的时候的最大分数，同时得到各个子树i的最大分数dp\[i\]。然后利用前面得到的dp数组分别计算以其他每个点作为根的时候的最大分数。

**实现：**

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const int N = 200005;
     5 vector<int> G[N];
     6 ll cnt[N], dp[N];
     7 int n;
     8 void dfs(int u, int p)
     9 {
    10     cnt[u] = 1;
    11     for (int i = 0; i < G[u].size(); i++)
    12     {
    13         int t = G[u][i];
    14         if (t == p) continue;
    15         dfs(t, u);
    16         cnt[u] += cnt[t];
    17         dp[u] += dp[t];
    18     }
    19     dp[u] += cnt[u];
    20 }
    21 void dfs2(int u, int p, ll x, ll& ans)
    22 {
    23     ans = max(ans, dp[u] - cnt[u] + x + n);
    24     for (int i = 0; i < G[u].size(); i++)
    25     {
    26         int t = G[u][i];
    27         if (t == p) continue;
    28         dfs2(t, u, dp[u] - cnt[u] - dp[t] + x + n - cnt[t], ans);
    29     }
    30 }
    31 int main()
    32 {
    33     int a, b;
    34     while (cin >> n)
    35     {
    36         for (int i = 1; i <= n; i++) G[i].clear();
    37         memset(cnt, 0, sizeof cnt); memset(dp, 0, sizeof dp);
    38         for (int i = 1; i <= n - 1; i++)
    39         {
    40             cin >> a >> b;
    41             G[a].push_back(b); G[b].push_back(a);
    42         }
    43         dfs(1, 0);
    44         ll maxn = dp[1];
    45         for (int i = 0; i < G[1].size(); i++)
    46         {
    47             int t = G[1][i];
    48             dfs2(t, 1, dp[1] - dp[t] - cnt[t], maxn);
    49         }
    50         cout << maxn << endl;
    51     }
    52     return 0;
    53 }

转载于:https://www.cnblogs.com/wangyiming/p/11127623.html