题解：P15970 树上检查
_cout_
·
·
题解
审核题解，管理员辛苦了。
首先 k\le 2 是简单的，k=1 输出 n，k=2 输出 C_n^2。
我们先考虑 k=3，不难发现一个选点方式答案要么是 1，要么是 2，而贡献为 1 的方案就是选的点可以在一条简单路径上。
我们设贡献为 1 的选点方案为 s（显然在一条路径上更好算），那么答案就是 s+2\times (C_n^k-s) 也就是 2\times C_n^k-s。
我们先考虑 k=3 的情况，我们钦定贡献计算在简单路径上的端点，且端点必选（防止算重）。
那么 s=\sum_{u<v} d(u,v)-1 其中 d(u,v) 表示 u 与 v 之间的距离（边数）。
我们现在只要算出 $\sum d$ 即可，这显然是好做的，直接换根即可。
我们考虑 $k=4$，$s=\sum_{u<v} C_{d(u,v)-1}^2$ 直接展开组合数变为只跟 $d^2$，$d$，有关的式子，同理直接换根即可。
换根式子很好推，就不推了（注意算出来的值需要除以 $2$）。
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int k,ans,dis;
int sz[200005],fac[200005],sq[200005],dep[200005],dp[200005],dp2[200005],dep2[200005];
vector <int> mp[200005];
int n;
int C(int n,int m)
{
if(n<m)
return 0;
return fac[n]*sq[n-m]%mod*sq[m]%mod;
}
int qpow(int x,int y)
{
int res=1;
while(y)
{
if(y&1)
{
res=res*x%mod;
}
x=x*x%mod;
y>>=1;
}
return res;
}
void init(int u,int fa)
{
sz[u]=1;
for(int i=0;i<mp[u].size();i++)
{
int v=mp[u][i];
if(v==fa)
continue;
init(v,u);
sz[u]+=sz[v];
dep[u]+=sz[v]+dep[v];
dep[u]%=mod;
dep2[u]+=dep2[v]+2*dep[v]+sz[v];
dep2[u]%=mod;
}
}
void dfs(int u,int fa)
{
for(int i=0;i<mp[u].size();i++)
{
int v=mp[u][i];
if(v==fa)
continue;
dp[v]=dp[u]-sz[v]+n-sz[v];
dp2[v]=dp2[u]+2*dp[u]+n-4*(dep[v]+sz[v]);
dp2[v]=(dp2[v]%mod+mod)%mod;
dfs(v,u);
}
}
signed main()
{
fac[0]=sq[0]=1;
for(int i=1;i<=200004;i++)
fac[i]=fac[i-1]*i%mod,sq[i]=qpow(fac[i],mod-2);
int t;
cin>>t;
while(t--)
{
cin>>n>>k;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
mp[u].push_back(v);
mp[v].push_back(u);
}
if(k==1)
cout<<n<<endl;
if(k==2)
cout<<n*(n-1)/2%mod<<endl;
init(1,0);
int sumd=0;
dp[1]=dep[1];
dp2[1]=dep2[1];
dfs(1,0);
if(k==3)
{
for(int i=1;i<=n;i++)
sumd+=dp[i],sumd%=mod;
cout<<(2*C(n,3)-sumd*sq[2]%mod+C(n,2)%mod+mod)%mod<<endl;
}
if(k==4)
{
int sumd2=0;
for(int i=1;i<=n;i++)
sumd+=dp[i],sumd%=mod,sumd2+=dp2[i],sumd2%=mod;
cout<<((2*C(n,4)-(sumd2*sq[2]%mod*sq[2]%mod-3*sumd*sq[2]%mod*sq[2]%mod+C(n,2)%mod))%mod+mod)%mod<<endl;
}
ans=0;
for(int i=1;i<=n;i++)
mp[i].clear(),sz[i]=dep[i]=dp[i]=dep2[i]=dp2[i]=0;
}
}
```