杭电多校6 F - Maex （树形DP）

 input：

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

output：

8
6
1

题目大意：给我们一棵树，让我们给树上的每个结点设计一个权值，对于每个结点i有这样一个定义：b[i]是以i为根节点的子树中最小的没有出现过的非负整数，让我们求出所有结点b数组的值之和最大是多少。

解题思路：因为b数组是对应子树中没有出现过的最小的非负整数，而最小的非负整数是0，所以为了让b数组的值尽可能大，一棵子树中应该尽可能包含0，1，2，3……这种按顺序从大到小的数字，并且数字越小就越应该放在更底层的子树中，这样就保证了从底层往上，结点对应b数组的值就越来越大，而我们可以发现b数组的值恰好就是以该点为根的子树中结点的数目，所以我们的思路就是在树中找一条链，使得分别以这条链上每一个结点为根的子树大小之和最大，所以我们可以先dfs预处理出以该点为根的子树中包含的结点数目，然后再进行第二遍dfs得到一条链上所能获得的最大权值之和。

上代码：

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N=5e5+10;
int a[N],n,h[N],e[N<<1],ne[N<<1],idx,depth[N];
void add(int u,int v)
{
	e[idx]=v;
	ne[idx]=h[u];
	h[u]=idx++;
}
long long dp[N],du[N],ans=-0x3f3f3f3f,maxv[N];
void dfs(int u,int fa)
{
	dp[u]=1;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa)
		continue;
		dfs(j,u);
		dp[u]+=dp[j];
	}
}
void dfs_u(int u,int fa)
{
	if(fa==-1)
	maxv[u]=dp[u];
	else
	maxv[u]=dp[u]+maxv[fa];
	if(du[u]==1)
	{
		ans=max(ans,maxv[u]);
	}
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa)
		continue;
		dfs_u(j,u);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		if(n==1)
		{
			cout<<1<
			continue;
		}
		memset(h,-1,sizeof h);
		memset(du,0,sizeof du);
		memset(maxv,0,sizeof maxv);
		memset(dp,0,sizeof dp);
		idx=0;
		
		ans=-0x3f3f3f3f;
		for(int i=1;i
		{
			int  u,v;
			cin>>u>>v;
			add(u,v);
			du[v]++;
			add(v,u);
			du[u]++;
		}
		dfs(1,-1);
		dfs_u(1,-1); 
		cout<
	}
	return 0;
 }