题目

题目描述

给定一个 $n$ 个点的树，每个点的编号从 $1$ 至 $n$ ，问这个树有多少不同的连通子树，和这个树有相同的重心
其中 $n$ 个点的树指的是 $n$ 个点的最小连通图，显然 $n$ 个点的树有 $n-1$ 条边，去掉这 $n-1$ 条边中的任何一条，原图都不再联通，任意两个点之间由唯一一条路径相连
对于一个树，树的重心定义为：删掉某点 $i$ 后，若剩余 $k$ 个连通分量，那么定义 $d(i)$ 为这些连通分量中点的个数的最大值，所谓重心，就是使得 $d(i)$ 最小的点 $i$
基于以上定义，一个树的重心可能会有一个或者两个，题中所要求的联通子树，其重心编号和个数必须和原树的完全一样
编程任务：找出给定的树中有多少连通的子树和这个树有相同的重心

输入格式

第1行：正整数 $Q$ ，表示该组数据中有多少组测试样例
每组样例首先输入一个整数 $n (0 < n \leqslant 200)$ ，表示该组样例中输入的树包含 $n$ 个点
之后 $n-1$ 行，每行输入两整数数 $x, y(1 \leqslant x , y \leqslant n )$ ，表示编号为 $x$ 的点和编号为 $y$ 的点之间存在一条边，所有点的编号从 $1$ 到 $n$

输出格式

首先输出样例编号，之后输出满足条件的子树的个数，由于这个数字较大，你只需要输出这个数字对 $10007$ 取模后的结果，即 $mod 10007$
详见输出示例，请严格按照输出实例中的格式输出

样例

样例输入

样例输出

Case 1: 1
Case 2: 2
Case 3: 6

数据范围与提示

$20\%$ 的数据满足 $n\leqslant 10$
$10\%$ 的数据满足给定的树中任意一个节点最多只有两个相邻节点
$100\%$ 的数据满足 $Q\leqslant 50, n\leqslant 200$

题解

我们可以分别讨论1个和2个两个中心的情况：

1个：考虑用树形dp来求最终的答案，直接以重心为根，枚举节点数，用 $f_{i,j}$ 表示以 $i$ 为根，选 $j$ 个节点的答案数，dp的状态转移和洛谷P4322&&BZOJ4753&&DTOJ3156 最佳团体有点像
2个：直接对两个重心分别求出答案，利用乘法原理求出最终的答案

附上代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,tot,root,ans,MOD=10007,head[210],big[210],size[210],f[210][210],temp[210];
struct ppap
{
    int to,nxt;
}e[410];
void add(int u,int v)
{
    e[++tot].nxt=head[u],e[tot].to=v,head[u]=tot;
}
void getroot(int x,int fa)
{
    size[x]=1,big[x]=0;
    for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa)
        getroot(e[i].to,x),size[x]+=size[e[i].to],big[x]=max(big[x],size[e[i].to]);
    big[x]=max(big[x],n-size[x]);
    if(big[x]<=big[root]||(!root)) root=x;
}
void dfs(int x,int fa)
{
    size[x]=f[x][0]=f[x][1]=1;
    for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa){ 
        dfs(e[i].to,x);
        for(int j=1;j<=size[x]+size[e[i].to];j++) temp[j]=0;
        for(int j=1;j<=size[x];j++) for(int k=0;k<=size[e[i].to];k++)
            temp[j+k]=(temp[j+k]+f[x][j]*f[e[i].to][k]%MOD)%MOD;
        size[x]+=size[e[i].to];
        for(int j=1;j<=size[x];j++) f[x][j]=temp[j];
    }
}
void solve1(int x)
{
    memset(f,0,sizeof(f));
    dfs(x,0);
    for(int i=1;i<=n;i++){
        memset(f[x],0,sizeof(f[x])),size[x]=f[x][0]=f[x][1]=1;
        for(int j=head[x];j;j=e[j].nxt){
            for(int k=1;k<=size[x]+size[e[j].to];k++) temp[k]=0;
            for(int k=1;k<=size[x];k++) for(int l=0;l<=size[e[j].to];l++){
                if(l*2>=i) break;
                temp[k+l]=(temp[k+l]+f[x][k]*f[e[j].to][l]%MOD)%MOD;
            }
            size[x]+=size[e[j].to];
            for(int k=1;k<=size[x];k++) f[x][k]=temp[k];
        }
        ans=(ans+f[x][i])%MOD;
    }
}
void solve2(int x,int y)
{
    memset(f,0,sizeof(f));
    dfs(x,y),dfs(y,x);
    for(int i=1;i<=n;i++) ans=(ans+f[x][i]*f[y][i]%MOD)%MOD;
}
int main()
{
    int test=0,T;
    scanf("%d",&T);
    while(T--){
        test++,memset(head,0,sizeof(head)),tot=ans=0;
        scanf("%d",&n);
        for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
        root=0,getroot(1,0);
        if(big[root]*2<n) solve1(root);
        else{
            int y;
            for(int i=head[root];i>0;i=e[i].nxt){
                y=e[i].to;
                if(big[root]==size[y]) break;
            }
            solve2(root,y);
        }
        printf("Case %d: %d\n",test,ans);
    }
}