题目描述
You are given a tree with $ n $ nodes. For each node, you either color it in $ 0 $ or $ 1 $ .
The value of a path $ (u,v) $ is equal to the MEX $ ^\dagger $ of the colors of the nodes from the shortest path between $ u $ and $ v $ .
The value of a coloring is equal to the sum of values of all paths $ (u,v) $ such that $ 1 \leq u \leq v \leq n $ .
What is the maximum possible value of any coloring of the tree?
$ ^{\dagger} $ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:
- The MEX of $ [2,2,1] $ is $ 0 $ , because $ 0 $ does not belong to the array.
- The MEX of $ [3,1,0,1] $ is $ 2 $ , because $ 0 $ and $ 1 $ belong to the array, but $ 2 $ does not.
- The MEX of $ [0,3,1,2] $ is $ 4 $ because $ 0 $ , $ 1 $ , $ 2 $ , and $ 3 $ belong to the array, but $ 4 $ does not.
输入格式
Each test contains multiple test cases. The first line of input contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of nodes in the tree.
The following $ n-1 $ lines of each test case contains $ 2 $ integers $ a_i $ and $ b_i $ ( $ 1 \leq a_i, b_i \leq n, a_i \neq b_i $ ) — indicating an edge between vertices $ a_i $ and $ b_i $ . It is guaranteed that the given edges form a tree.
It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ .
考虑 dp。
正着dp 不好做，先设所有的路径的 mex 都是 2,然后减去不为 2 的路径的贡献。
路径的 mex 不为 2，当且仅当两个路径在一个同色连通块中。
考虑对极大同色连通块进行 dp，一个极大 \(j\) 色连通块的贡献是 \(\frac{i(i+1)(j+1)}2\)
发现黑白染色的代价是 \(1.5n\) 左右的，所以最优方案里极大同色连通块是 \(O(\sqrt{n})\) 级别的。
所以可以直接树形dp，可以证明总复杂度是 \(O(\sqrt{n})\) 的。
但是空间开不下？
儿子节点只会在父亲时才会 dp 到，所以父亲用完就释放掉。由于一个点只开了 \(sz_x\) 大小的数组，所以空间是 \(O(n)\) 的。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,INF=1e9;
int t,n,hd[N],e_num,sz[N],ss;
vector<int>dp[N][2];
int ans;
struct edge{
int v,nxt;
}e[N<<1];
int read()
{
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s;
}
void add_edge(int u,int v)
{
e[++e_num]=(edge){v,hd[u]};
hd[u]=e_num;
e[++e_num]=(edge){u,hd[v]};
hd[v]=e_num;
}
void dfs(int x,int y)
{
sz[x]=1;
dp[x][0].resize(2);
dp[x][1].resize(2);
for(int i=hd[x];i;i=e[i].nxt)
{
if(e[i].v==y)
continue;
dfs(e[i].v,x);
dp[x][0].resize(min(ss,sz[x]+sz[e[i].v]+1),INF),dp[x][1].resize(min(ss,sz[x]+sz[e[i].v]+1),INF);
int r1=INF,r2=INF;
for(int j=1;j<dp[e[i].v][0].size();j++)
{
r1=min(r1,dp[e[i].v][0][j]+j*(j+1)/2);
r2=min(r2,dp[e[i].v][1][j]+j*(j+1));
}
for(int k=dp[x][0].size()-1;k;k--)
{
dp[x][0][k]+=r2;
dp[x][1][k]+=r1;
for(int j=max(1,k-sz[x]);j<k&&j<dp[e[i].v][0].size();j++)
{
dp[x][0][k]=min(dp[x][0][k],dp[e[i].v][0][j]+dp[x][0][k-j]);
dp[x][1][k]=min(dp[x][1][k],dp[e[i].v][1][j]+dp[x][1][k-j]);
}
}
dp[e[i].v][0].clear(),dp[e[i].v][1].clear();
dp[e[i].v][0].shrink_to_fit(),dp[e[i].v][1].shrink_to_fit();
sz[x]+=sz[e[i].v];
}
}
int main()
{
t=read();
while(t--)
{
n=read();
ss=sqrt(n)*2;
for(int i=1;i<=n;i++)
{
dp[i][0].clear(),dp[i][0].shrink_to_fit();
dp[i][1].clear(),dp[i][1].shrink_to_fit();
hd[i]=0;
}
e_num=0;
for(int i=1;i<n;i++)
add_edge(read(),read());
dfs(1,0);
ans=INF;
for(int i=1;i<dp[1][1].size();i++)
ans=min({ans,dp[1][0][i]+i*(i+1)/2,dp[1][1][i]+i*(i+1)});
printf("%lld\n",n*(n+1LL)-ans);
}
}