原题链接：Problem - 7202

题目大意：

给定一个n个结点的有根树，根为1，每个结点有一个唯一的自然数权值，定义b[u]为MEX{顶点u的子树}。一个集合的MEX为不属于这个集合的最大非负整数。求出这棵树最大的b[i]之和。（怎样给每个结点赋权值，能够使得b[i]之和最大）

题目描述：

You are given a rooted tree consisting of n vertices numbered from 1 to n, and the root is vertex 1.
Vertex i has a natural number weight a i , and no two different vertexes have the same weight.
Define b[u] = MEX{x|∃v ∈ subtree(u),x = a[v] }.
Unfortunately, a[i] are not given. Please find out the maximum possible sum of b[i]
The MEX of a set is the minimum non-negative integer that doesn’t belong to the set.

解题思路：

用 siz[u]表示 子树节点个数， dp[u]表示u子树内sum(bi)可以达到的最大值。
那么考虑转移， u本身的b[u]一定可以是siz[u]，而因为顶点权值必须两两不同，0只能在u的某个子树内，所以除了某个子树，其他子树节点的b[i]一定都为0.
那么转移就是：

dp[u] = size[u] + max(dp[v]) (vsubtree(u))

建议在纸上画一画模拟一下，会比较直观。

代码（CPP）：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 5e5 + 10;
vector<int> G[maxn];
ull n, siz[maxn], dp[maxn];
bool vis[maxn];

void dfs(int u)
{
    vis[u] = true;
    siz[u] = 1;
    ull Max = 0;
    dp[u] = 0;
    for (int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if(!vis[v])
        {
            dfs(v);
            siz[u] += siz[v];
            Max = max(Max, dp[v]);
        }   
    }
    dp[u] = Max + siz[u];
}

int main()
{                                       
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        for (int i = 0; i < maxn; i++)
        {
            G[i].clear();
        }
        memset(vis, 0, sizeof vis);
        cin >> n;
        ull m = n - 1;
        while(m--)
        {
            int u, v;
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1);
        cout << dp[1] << "\n";
    }
    return 0;
}