[树形dp]Maex 2022杭电多校第6场 1006

Problem Description

You are given a rooted tree consisting of nn vertices numbered from 11 to nn, and the root is vertex 11.

Vertex ii has a natural number weight a_iai​, and \textbf{no two different vertexes have the same weight}no two different vertexes have the same weight.

Define b_u = MEXbu​=MEX { x \space | \space \exists v \in subtree\left( u \right), x = a_vx ∣ ∃v∈subtree(u),x=av​}.

Unfortunately, a_iai​ are not given. Please find out the maximum possible \sum_{i=1}^{n}b_i∑i=1n​bi​.

The \textbf{MEX}MEX of a set is the minimum non-negative integer that doesn't belong to the set.

Input

The first line contains one integer T \left( 1 \leq T \leq 10 \right)T(1≤T≤10), indicating the number of test cases.

For each test case:

The first line contains one integer n \left( 1 \le n \le 5 \cdot 10^5 \right)n(1≤n≤5⋅105), indicating the number of nodes.

In the following n-1n−1 lines, each line contains two interger u, v \left(1 \le u, v \le n \right)u,v(1≤u,v≤n), indicating an edge \left( u, v \right)(u,v) of the tree.

A guarantee is that forming trees.

Output

For each test case: One line with an integer, indicating the maximum possible \sum_{i=1}^{n}b_i∑i=1n​bi​.

Sample Input

3

5

1 2

3 2

1 5

4 1

3

1 2

2 3

1

Sample Output

8

6

1

题意： 给出一棵树，树上各点都有一个点权ai，还各有一个价值bi，bi的值是点i子树中a值集合的MEX，ai的值可以为任意自然数，并且各ai值不同，求bi加和的最大值。

分析： 根据样例模拟一下可知，只有从根节点到某个叶子结点路径上的点才会对答案有贡献，而且这个贡献值一定是该点子树中点的个数，可以设状态dp[i]表示在以i为根的子树中得到的b加和最大值，显然初始状态也就是叶子结点的dp值为1，之后当前结点now的dp值可以由子结点dp值加上子树中点个数得到，显然我们应该选取dp值最大的那个子结点，最后答案就是dp[1]。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define int long long 
using namespace std;
 
vector<int> tr[500005];
int num[500005], dp[500005];
 
void dfs(int now, int fa){
	int mx = 0;
	for(int i = 0; i < tr[now].size(); i++){
		int to = tr[now][i];
		if(to == fa) continue;
		dfs(to, now);
		num[now] += num[to]+1;
		mx = max(mx, dp[to]);
	}
	dp[now] = mx+num[now]+1;
}
 
signed main()
{
	int T;
	cin >> T;
	while(T--){
		int n;
		scanf("%lld", &n);
		for(int i = 1; i <= n; i++){
			dp[i] = 0;
			num[i] = 0;
			tr[i].clear();
		}
		for(int i = 1; i < n; i++){
			int u, v;
			scanf("%lld%lld", &u, &v);
			tr[u].push_back(v);
			tr[v].push_back(u);
		}
		dfs(1, 0);
		printf("%lld\n", dp[1]);
	} 
    return 0;
}