A 好数（number）
开桶记录。
B SOS字符串（sos）
\(f_{i,j,k,n}\) 表示到 \(i\)，结尾两个字母是 \(j,k\)，已经有了 \(0/1/2\) 个 SOS，字母有 \(4\) 类，分别为 O，没用过的 S，无用字母 X，用过的 S，的方案数，转移暴力。
C 集训营的气球（balloon）
首先有暴力背包，然后每次修改看成删除一个，添加一个，就成退背包的板子了。退背包从小到大退，保证了正确性。
D 连通子树与树的重心（tree）
题目中的子树含义是连通块，所以下面也是。
两种情况：第一种，两个重心，两个重心一定在一起，且他们子树的最大值恰好为 \(\frac{n}{2}\)，整个子树大小相同，否则重心不能移动，只有一个。
对于这种情况只需要知道重心所在连通块大小的方案数就好了，设 \(f_{i,j}\) 表示以 \(i\) 为根，子树大小为 \(j\) 的方案数，树上背包转移，然后答案就是 \(\sum_{i=1}^{\frac{n}{2}}f_{rt1,i}f_{rt2,i}\)，时间复杂度 \(\mathcal{O}(n^2)\)。
第二种情况，只有一个重心，设 \(g_{i,j}\) 表示以这个重心为根，联通块大小为 \(i\)，且最大子树大小为 \(j\) 的方案数。答案就是 \(\sum_{i=1}^{n}\sum_{j=0}^{\frac{n}{2}-1}g_{i,j}\)，如果等于的话就会有两个重心。借助 \(f\)，可以再次背包出 \(g\)，时间复杂度 \(\mathcal{O}(n^3)\)。
发现合法情况有很多，而不合法情况很少，因为只会有一个子树大小大于等于 \(\frac{size}{2}\)，所以统计所有不合法的情况，最后减去即可。还是借助 \(f\)，枚举重心的儿子作为不合法的情况，如果直接暴力重新背包时间复杂度还是 \(\mathcal{O}(n^3)\) 的，所以退背包求出不用每个儿子的方案，然后统计逐个统计即可。
#include<bits/stdc++.h>
#define pii std::pair<int,int>
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=5e3+10,mod=10007;
int n,size[N],RT[2],num,d[N][N],f[N][N],ans;
std::vector<int> e[N];
inline void findrt(int x,int fa){
size[x]=1;int max=0;
for(int v:e[x]){
if(v==fa)continue;
findrt(v,x);size[x]+=size[v];max=std::max(max,size[v]);
}max=std::max(max,n-size[x]);
if(max<=n/2)RT[num++]=x;
}
inline void dfs(int x,int fa){
d[x][1]=1;size[x]=1;
for(int v:e[x]){
if(v==fa)continue;
dfs(v,x);
for(int i=size[x];i;--i)for(int j=size[v];j;--j)d[x][i+j]=(d[x][i+j]+d[x][i]*d[v][j])%mod;
size[x]+=size[v];
}
}
inline void sub1(){
dfs(RT[0],RT[1]);dfs(RT[1],RT[0]);
for(int i=1;i<=n/2;++i)ans=(ans+d[RT[0]][i]*d[RT[1]][i])%mod;
}
inline void sub2(){
dfs(RT[0],0);
memset(f,0,sizeof(f));
for(int v:e[RT[0]]){
for(int i=1;i<=n;++i){
f[v][i]=d[RT[0]][i];
for(int j=1;j<=std::min(i,size[v]);++j)f[v][i]=(f[v][i]-f[v][i-j]*d[v][j])%mod;
}
}
for(int i=1;i<=n;++i){
ans=(ans+d[RT[0]][i])%mod;
for(int v:e[RT[0]]){
for(int j=(i+1)/2;j<=std::min(i,size[v]);++j)
ans=(ans-d[v][j]*f[v][i-j])%mod;
}
}
ans=(ans%mod+mod)%mod;
}
signed main(){
// freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
ans=0,num=0;
n=read();for(int i=1;i<n;++i){int u=read(),v=read();e[u].eb(v);e[v].eb(u);}
findrt(1,0);
if(num==2)sub1();
else sub2();
std::cout<<ans<<'\n';
}