题意
题目链接。
使用 coze.com 的 gpt-4 进行翻译和格式美化.
给定一个包含$N$个顶点的树$T$，设$F$是$T$的顶点的一个子集，如果$F$满足以下条件，则称$F$为$x$根火花：
- $F$包含顶点$x$ – $F$是$T$的连通子图——也就是说，由$F$导出的子图$T[F]$是连通的。
- 令$d_F(u)$表示节点$u$在$T[F]$中的度。然后，对于所有$y \in F$，并且$y \neq x$，$d_F(y) \leq 2$应成立。也就是说，在$F$中，不是$x$的每个顶点最多应该有两个邻居。
- 令$d_T(u)$表示节点$u$在$T$图中的度。然后，对于所有$y \in F$并且$y \neq x$，$d_T(y) \neq d_T(x)$应成立。
图$G$中节点的度是与其在$G$中的边的数量。
对于从$1$到$N$的每个$x$，找到$x$根火花的最大大小。
解析
一个很有趣的题目。
不妨先考虑对于一个点 $u$ 怎么统计答案。首先我们发现由于最终图除 $u$ 外的所有点的度数不多于 $2$，所以最大火花显然是一个以 $u$ 为中心的星形图。记点 $u$ 的度数为 $d_u$，我们可以删除树中所有度为 $d_u$ 的点，然后原树被分割成了一个由若干树组成的森林。对于与 $u$ 相连的每一个点，我们计算这个点在分割后其所在的树上能到达的最远距离，记这条最长路上点的数量为 $dis_v$。则 $ans_u=1+ \sum dis_v$。
既然我们删除了所有度为 $d_u$ 的点，我们不妨统计所有度为 $d_u$ 点的答案。即，我们枚举度数 $k$，删除所有度数为 $k$ 的点。然后计算出所有度不为 $k$ 的点在其分割后所在的树上的 $dis_u$，接着我们再用上段的方法对所有度数为 $k$ 的点统计答案即可。
根据 DP on Trees – Solving For All Roots 提供的 dp 方法，或者是求树的直径的方法。我们可以在 $O(n)$ 计算所有点的 $dis_u$，同时我们也可以在 $O(n)$ 的时间内统计所有度数为 $k$ 的点的答案（因为每条边最多被访问两次）。
然后我们发现复杂度是正确的。因为 $\sum_{i=1}^n =\frac{(1+n)n}{2}$，度数 $k$ 最多只有 $O(\sqrt n)$ 种可能的取值，故最终时间复杂度为 $O(n\sqrt n)$。
代码
#include<bits/stdc++.h>
#define ll long long
#define pi pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
using namespace std;
const int N=1e5+5;
const int M=2e5+5;
struct node{
int to,nxt;
}e[M];
int head[N],cnt;
void add(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int du[N],n,f[N],f2[N],g[N],ans[N];
void dfs(int u,int fa,int k){
if(du[u]==k) return;
f[u]=f2[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;if(v==fa) continue;
dfs(v,u,k);
if(f[v]+1>f2[u]) f2[u]=f[v]+1;
if(f2[u]>f[u]) swap(f[u],f2[u]);
}
}
void dfs2(int u,int fa,int k){
if(du[u]==k) return;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;if(v==fa||du[v]==k) continue;
if(f[v]+1==f[u]) g[v]=max(g[u]+1,f2[u]+1);
else g[v]=max(g[u]+1,f[u]+1);
dfs2(v,u,k);
}
}
void furthersolve(int k){
for(int i=1;i<=n;i++){f[i]=f2[i]=0;g[i]=1;}
for(int i=1;i<=n;i++){
if(du[i]==k||f[i]) continue;
dfs(i,i,k);dfs2(i,i,k);
}
for(int u=1;u<=n;u++){
if(du[u]!=k) continue;
ans[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;if(du[v]==k) continue;
//printf("%d %d %d\n",u,v,max(f[v],g[v]));
ans[u]+=max(f[v],g[v]);
}
}
}
void solve(){
scanf("%d",&n);cnt=0;
vector<int> vec[n+1];
for(int i=1;i<=n;i++){
head[i]=du[i]=0;
}
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
du[u]++;du[v]++;
}
for(int i=1;i<=n;i++) vec[du[i]].pb(i);
for(int i=1;i<=n;i++){
if(vec[i].empty()) continue;
furthersolve(i);
}
for(int i=1;i<=n;i++){
printf("%d ",ans[i]);
}
printf("\n");
}
signed main(){
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}