我们考虑这道题一看题就特别难受，所有路径？\(mex\) 之和？这是什么东西？
我们考虑 \(mex\) 之和其实是有一点诈骗的感觉，毕竟是 \(0\) 或 \(1\)，还比较简单。就是路径上全都是 \(1\) 的时候是 \(0\)，全都是 \(0\) 的时候是 \(1\)，有 \(0\) 和 \(1\) 的时候是 \(2\)。
\(n \leq 2 \times 10^5\) 显然是有点 DP 的影子，但是我们想设出一个状态还是很难的，毕竟很难规避它的后效性的问题，子树内的路径即使在子树内不优，但是有可能在外面更优。
如果真的记下当前的 只含 \(0\)、只含 \(1\)、含 \(0\) 和 \(1\) 的路径的个数，显然空间爆炸。
你考虑正难则反，我们考虑什么时候会损失 \(mex\) 之和，显然是链全为 \(1\) 或者全为 \(0\)。
我们正常 DP，设 \(f_{u,j,0/1}\) 表示以 \(u\) 为根的子树，当前点放的是 \(0/1\)，和点 \(u\) 相同颜色的和 \(u\) 直接相连的点的个数为 \(j\)，当前最少的损失是多少。
转移式子如下：
\[\begin{cases}
f_{u,j,0}=\min (f_{u,j,0}+\min\limits_{k}\{f_{v,k,1}\},\min\limits_{k}\{f_{u,k,0}+f_{v,j-k,0}+j(j-k)\})\\
f_{u,j,1}=\min (f_{u,j,1}+\min\limits_{k}\{f_{v,k,0}\},\min\limits_{k}\{f_{u,k,1}+f_{v,j-k,1}+2j(j-k)\})\\
\end{cases}
\]
- 为什么是 \(j(j-k)\)：考虑显然被影响的链的数量为 \(j(j-k)\)
- 为什么加上了 \(\min\limits_{k}\{f_{v,k,0/1}\}\)：因为左半部分计算的是当前儿子染异色，右半部分是染同色。
- 时间复杂度？：因为显然我们通过贪心之类的 算法可以构造出一个较优的解，就是进行黑白染色，然后可以发现所有长度大于等于 \(2\) 的链都是 \(2\) 的贡献，所以最多缺少的是 \(2n\)，所以实际上 \(j\) 这一维最多只需要开到 \(\sqrt {2n}\)，这个时候只需要代码优秀再加上使用优秀的
c++17即可通过，好像luogu上有 \(j\) 这一维只需要开到 \(300\) 的证明，有兴趣可以自己去看一看。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NN = 2e5 + 8,B = 300,INF = 1e18;
vector<ll> f[NN][2];
int n;
struct Edge{
int to,next;
}edge[NN << 1];
int head[NN],cnt;
void init(){
for(int i = 1; i <= n; ++i) head[i] = -1;
cnt = 1;
}
void add_edge(int u,int v){
edge[++cnt] = {v,head[u]};
head[u] = cnt;
}
ll siz[NN];
ll g[2][300];
void dfs(int u,int fa){
siz[u] = 1;
f[u][0].resize(2);f[u][1].resize(2);
f[u][0][0] = f[u][1][0] = INF;f[u][0][1] = 1;f[u][1][1] = 2;
for(int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].to;
if(fa == v) continue;
dfs(v,u);
siz[u] += siz[v];
ll min0 = INF,min1 = INF;
for(int j = 1; j <= min(B,siz[v]); ++j) min0 = min(min0,f[v][0][j]),min1 = min(min1,f[v][1][j]);
for(int j = 1; j <= min(B,siz[u]-siz[v]); ++j) g[1][j] = f[u][1][j],g[0][j] = f[u][0][j];
f[u][0].resize(min(B,siz[u])+1);f[u][1].resize(min(B,siz[u])+1);
for(int j = 1; j <= min(B,siz[u]); ++j) f[u][0][j] = f[u][1][j] = INF;
for(ll j = 1; j <= min(B,siz[u]); ++j){
for(int k = max(1ll,j-min(B,siz[u]-siz[v])); k <= min(j-1,min(B,siz[v])); ++k){
f[u][0][j] = min(f[u][0][j], g[0][j-k] + f[v][0][k] + k * (j-k));
f[u][1][j] = min(f[u][1][j], g[1][j-k] + f[v][1][k] + 2 * k * (j-k));
}
}
for(int j = 1; j <= min(B,siz[u]-siz[v]); ++j){
f[u][0][j] = min(g[0][j]+min1,f[u][0][j]);
f[u][1][j] = min(g[1][j]+min0,f[u][1][j]);
}
f[v][0].clear(); f[v][0].shrink_to_fit(); f[v][1].clear(); f[v][1].shrink_to_fit();
}
}
int t;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);init();
for(int i = 1,u,v; i < n; ++i){
f[i][0].clear();f[i][1].clear();
scanf("%d%d",&u,&v);
add_edge(u,v);add_edge(v,u);
}
f[n][0].clear();f[n][1].clear();
dfs(1,1);
ll ans = INF;
for(int i = 1; i <= min(B,siz[1]); ++i) ans = min(ans,min(f[1][0][i],f[1][1][i]));
printf("%lld\n",1ll * n * (n+1) - ans);
}
}