学好数理化，走遍天下都不怕

洛谷P4582 BZOJ4015 DTOJ1748 [FJOI2014]树的重心

发表于 更新于 分类于

题目

题目描述

给定一个$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$
详见输出示例，请严格按照输出实例中的格式输出

样例

样例输入

1
2
3
4
5
6
7
8
9
10
11
3
2
1 2
3
1 3 
2 3
5
1 2
1 3
2 4
2 5

样例输出

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

数据范围与提示

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

题解

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

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

附上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#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);
    }
}