2022杭电多校六 1006-Maex （树形DP）

题目链接：https://vjudge.net/contest/508623#problem/F

题目：

 样例输入：

3
5
1 2
3 2
1 5
4 1
3
1 2
2 3
1

样例输出：

8
6
1

题意：给你一个n个节点的有根树，根节点是1，我们可以给n个节点每个节点一个权值，但是任意两个节点的权值是不能相同的，定义bi为以第i个节点为根的子树中所有节点权值的mex值，的问我们的最大值。

因为每个节点的权值必须两两不同，0只能在某个子树内，所以除了这个子树之外的其他节点所对应的b一定为0，所以我们可以尽可能让这棵子树之内的所有点的权值尽可能连续，那么我们根节点的b值就大。我们可以令f[i]表示以i节点为根的子树中所有节点的mex之和最大值是多少，再用一个cnt[i]记录以i节点为根的子树中所有节点的个数是多少，那么我们直接进行动态转移即可：f[u]=cnt[u]+max(f[v])其中v是u的子节点。

细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=5e6+10;
int e[N],ne[N],h[N],idx;
int cnt[N];
long long f[N];//f[i]记录以i节点为根的子树中所有节点的mex之和的最大值
void add(int x,int y)
{
	e[idx]=y;
	ne[idx]=h[x];
	h[x]=idx++;
}
void dfs(int x,int fa)
{
	cnt[x]=1;
	long long t=0;//记录子节点贡献最大值 
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa) continue;
		dfs(j,x);
		cnt[x]+=cnt[j];
		t=max(f[j],t);
	}
	f[x]=cnt[x]+t;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		idx=0;
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) h[i]=-1; 
		int u,v;
		for(int i=1;i<n;i++)
		{
			scanf("%d%d",&u,&v);
			add(u,v);add(v,u);
		}
		dfs(1,-1);
		printf("%lld\n",f[1]);
	}
	return 0; 
}