【树形DP】CF 1293E Xenon's Attack on the Gangs

题目大意

vjudge链接
给n个结点，n-1条无向边。即一棵树。
我们需要给这n-1条边赋上0~ n-2不重复的值。
mex(u,v)表示从结点u到结点v经过的边权值中没有出现的最小非负整数。
计算下面等式的最大值：

\(s=\sum_{1\le u \le v \le n} mex(u,v)\)

样例1输入

3
1 2
2 3

样例1输出

3

样例2输入

5
1 2
1 3
1 4
3 5

样例2输出

10

思路

在b站找到了一个视频题解我觉得写的贼好……
链接
\(s=\sum_{1\le u \le v \le n} mex(u,v)=\sum_{1\le x \le n} (\sum_{mex(u,v)=x} x)=\sum_{1\le x \le n} (\sum_{mex(u,v)\ge x} 1)\)
只需要考虑每条边的贡献即可。
设0所在的边的两个端点u,v，则0的贡献为size[v][u]*size[u][v]。
接着看1，只有将0,1连接在一起贡献才会更大，所以我们要使得[0,m]分布在一条链上。
所以树形dp,dp[u][v]表示以u,v为端点的链。

【树形DP】CF 1293E Xenon's Attack on the Gangs

原文：https://www.cnblogs.com/Midoria7/p/12678656.html