树的重心。
定义
- 如果以重心为根，那么所有子树的大小都不超过整棵树的一半。
- 即以重心为根计算的最大子树节点数，是以其他点为根计算的最大子树节点数中最小的。
- 树的重心要么一个，要么最多两个。
- 树有两个重心时，我们保证两重心相邻，而且各自子树（加重心自己）的节点数=n/2，平分了这棵树
寻找重心思路
利用定义，我们遍历i点时，就记录他的最大子树节点数，如果他的数量<=n/2，那么他就是重心
注意到节点还有一颗子树是在他头上，因为我们已经求出i的所有子树节点，那么头上那颗节点数自然知道，就是n-cnt[i](cnt包括i自己）
void dfs(int u,int f)//寻找重心
{cnt[u]=1;//记录含u在内的以u为根的子树节点数int maxn=0;for(auto v:edge[u])if(v!=f){dfs(v,u);maxn=max(maxn,cnt[v]);//取最大子树节点数cnt[u]+=cnt[v];}maxn=max(maxn,n-cnt[u]);if(maxn<=n/2){root[root[0]!=-1]=u;//记录第一个重心（或者第二个重心）}
}Problem - 4863 (hdu.edu.cn)
思路：
- 首先，当然是求出重心的位置
- 对于子树节点数的方案数，我们可以用dp[u][j]记录以u为根有j个节点（包括u自己）的方案数
- 分类讨论重心
- 如果是有两个重心，显然各自重心两边节点数相同，直径累加乘积即可
- 如果只有一个重心，如果我们还是累加，显然要删去不合法的情况。
- 而对于n<=200来说，求非法情况还是很容易的
- 先说说怎么就不合法啦，如果以当前v子树为最大子树，那么显然如果cnt[v]大于其他子树节点和，不合法（重心定义）
- 设重心为rt，v子树为假设的最大子树，我们需要求出v子树外面的其他各类节点数对应的方案数。
- 用fdp[fv][j]存储v外面的节点数为j的方案数，我们可以枚举rt连接的其他儿子fv们，把每个儿子fv（节点数1~n的各种方案数)都看成一个背包，剩下就是背包知识了。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\\n"
const int N = 210;
const int mod=1e4+7;vector<int>edge[N];
int cnt[N],root[2];
int dp[N][N],fdp[N][N];
int n;
int pre(int b[])
{int ans=n;while(ans&&!b[ans])ans--;return ans;
}void dfs1(int u,int f)//寻找重心
{cnt[u]=1;int maxn=0;for(auto v:edge[u])if(v!=f)//记录含u在内的以u为根的子树节点数{dfs1(v,u);cnt[u]+=cnt[v];maxn=max(cnt[v],maxn);//取最大子树节点数}maxn=max(maxn,n-cnt[u]);if(maxn<=n/2)root[root[0]!=-1]=u;//记录第一个重心（或者第二个重心）
}void dfs(int u,int f)//求方案数
{dp[u][0]=dp[u][1]=1;for(auto v:edge[u])if(v!=f){dfs(v,u);int p1=pre(dp[u]),p2=pre(dp[v]);//预处理减少+0*0的浪费时间的情况for(int i=p1; i>=1; --i)for(int j=p2; j>=1; --j)dp[u][i+j]=(dp[u][i+j]+dp[u][i]*dp[v][j])%mod;//注意，u点至少也有自己，所以i>=1，v也一样，如果你节点数为0，我还加你干什么，所以j>=1}
}void solve1()//重心一个
{int ans=0,tmp=0;dfs(root[0],0);memset(fdp,0,sizeof(fdp));for(auto v:edge[root[0]])//求v外面的节点非法方案数{fdp[v][0]=1;for(auto fv:edge[root[0]])if(fv!=v)//注意，root的儿子不能是v，求的是v外面的节点{int p1=pre(fdp[v]),p2=pre(dp[fv]);for(int i=p1; i>=0; --i)for(int j=p2; j>=1; --j)fdp[v][i+j]=(fdp[v][i+j]+fdp[v][i]*dp[fv][j])%mod;//这里i可以从0开始，因为外面节点可以为0，j还是从1开始，不然加了没意义（还会错）}for(int i=1; i<=n; ++i)for(int j=0; j<i; ++j)tmp=(tmp+dp[v][i]*fdp[v][j])%mod;//v的节点数为i时，所有外面节点数和为j<i的都是不合法}for(int i=1; i<=n; ++i)ans=(ans+dp[root[0]][i])%mod;//计算所有情况ans=(ans-tmp+mod)%mod;//减去不合法情况cout<<ans<<endl;
}void solve2()//重心两个
{int ans=0;dfs(root[0],root[1]),dfs(root[1],root[0]);for(int i=1; i<=n; ++i)ans=(ans+dp[root[0]][i]*dp[root[1]][i])%mod;//直接累加相同的各自节点数乘积cout<<ans<<endl;
}int tt=0;
void mysolve()
{cin>>n;for(int i=1; i<=n; ++i)edge[i].clear();memset(dp,0,sizeof(dp));int x,y;for(int i=1; i<n; ++i)cin>>x>>y,edge[x].push_back(y),edge[y].push_back(x);root[0]=root[1]=-1;dfs1(1,0);cout<<"Case "<<++tt<<": ";if(root[1]==-1)solve1();else solve2();
}int32_t main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll t=1;cin >> t;while (t--){mysolve();}system("pause");return 0;
}