NC19953. [FJOI2014]树的重心
描述
输入描述
第1行中给出正整数Q，表示该组数据中有多少组测试样例。
每组样例首先输入一个整数n (0 < n ≤ 200)，表示该组样例中输入的树包含n个点，之后n-1行，每行输入两整数数x，y(1 ≤ x, y ≤ n)，表示编号为x的点和编号为y的点之间存在一条边，所有点的编号从1-n
输出描述
首先输出样例编号，之后输出满足条件的子树的个数，由于这个数字较大，你只需要输出这个数字对10007取模后的结果，即mod 10007，详见输出示例，请严格按照输出实例中的格式输出
示例1
输入:
3 2 1 2 3 1 2 2 3 5 1 2 1 3 2 4 2 5
输出:
Case 1: 1 Case 2: 2 Case 3: 6
C++14(g++5.4) 解法, 执行用时: 577ms, 内存消耗: 748K, 提交时间: 2020-10-21 15:35:19
#include <bits/stdc++.h>
#define LL long long
const int mod=10007;
using namespace std;
vector<vector<int> > G(205);
int sz[205], g[205], n;
int dfs(int u, int fa) {
int res=1<<30;
sz[u]=1, g[u]=0;
for(auto x: G[u]) {
if(x!=fa) {
res=min(res, dfs(x, u));
sz[u]+=sz[x], g[u]=max(g[u], sz[x]);
}
}
g[u]=max(g[u], n-sz[u]);
res=min(res, g[u]);
return res;
}
vector<int> root;//保存重心
int f[205][205], f1[205][205];
void DP(int u, int fa, int n) {
f[u][1]=1;
sz[u]=1;
for(auto x: G[u]) {
if(x==fa) continue;
DP(x, u, n);
for(int p=sz[u]; p>=1; p--) {
for(int q=min(sz[x], (n+1)/2-1); q>=1; q--) {
f[u][p+q]+=(f[u][p]*f[x][q])%mod;
f[u][p+q]%=mod;
}
}
sz[u]+=sz[x];
}
}
int main() {
int t, cas=1; scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i=1; i<=n; i++){
G[i].clear(); g[i]=0, sz[i]=0;
}
root.clear();
for(int i=2; i<=n; i++) {
int x, y;
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
int mi=dfs(1, 0);
for(int i=1; i<=n; i++) {
if(g[i]==mi) {
root.push_back(i);
}
}
LL ans=0;
if(root.size()==1) {
memset(sz, 0, sizeof(sz));
for(int sz=1; sz<=n; sz++) { //枚举siz的大小
memset(f, 0, sizeof(f));
DP(root[0], 0, sz);
ans+=f[root[0]][sz];
ans%=mod;
}
printf("Case %d: %lld\n", cas++, ans);
} else if(root.size()==2) {
memset(sz, 0, sizeof(sz));
memset(f, 0, sizeof(f));
DP(root[0], root[1], n);
memcpy(f1, f, sizeof(f));
memset(sz, 0, sizeof(sz));
memset(f, 0, sizeof(f));
DP(root[1], root[0], n);
for(int i=1; i<=n; i++){
ans=(ans+f[root[1]][i]*f1[root[0]][i]%mod)%mod;
}
printf("Case %d: %lld\n", cas++, ans);
}
}
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 307ms, 内存消耗: 1144K, 提交时间: 2022-09-14 20:08:08
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 207;
const int mod = 1e4+7;
const int INF = 0x3f3f3f3f;
int n;
struct Node{
int to,next;
}a[N<<1];
int last[N],tot;
int f[N][N],g[N],sz[N];
int F1[N][N];
void add(int u,int v){
tot++;
a[tot].to = v;
a[tot].next = last[u];
last[u] = tot;
}
int dfs1(int u,int fa){
int ans = INF;
sz[u] = 1;g[u] = 0;
for(int i = last[u];i>=0;i = a[i].next){
int v = a[i].to;
if(v==fa) continue;
ans = min(ans,dfs1(v,u));
sz[u]+=sz[v];g[u] = max(g[u],sz[v]);
}
g[u] = max(g[u],n-sz[u]);
ans = min(ans,g[u]);
return ans;
}
void dfs(int u,int fa){
sz[u]=f[u][0]=f[u][1]=1;
for(int z = last[u];z>=0;z = a[z].next){
int v = a[z].to;
if(v!=fa){
dfs(v,u),sz[u]+=sz[v];
for(int i=sz[u];i>=1;i--)
for(int j=1;j<=min(sz[v],i-1);j++)
(f[u][i]+=f[u][i-j]*f[v][j]%mod)%=mod;
}
}
}
int solve(){
cin>>n;
memset(last,-1,sizeof(last));
tot = -1;
int u,v;
for(int i = 1;i<=n-1;i++){
cin>>u>>v;
add(u,v);
add(v,u);
}
int ma = dfs1(1,0);
vector<int> G;
for(int i = 1;i<=n;i++) if(ma == g[i]) G.push_back(i);
int ans = 0,sum = 0;
if(G.size()==1){
memset(F1,0,sizeof(F1));
memset(f,0,sizeof(f));
dfs(G[0],0);
int ms = -INF;
for(int z = last[G[0]];z>=0;z = a[z].next){
int v = a[z].to;
ms = max(ms,sz[v]);
sum+=sz[v];
for(int i = sum;i>=1;i--){
for(int j = min(i,sz[v]);j>=1;j--){
if(j==i) (F1[i][j]+=f[v][j])%=mod;
else for(int k=1;k<=min(i,ms);k++)
(F1[i][max(j,k)]+=F1[i-j][k]*f[v][j]%mod)%=mod;
}
}
}
for(int i=1;i<=sum;i++)
for(int j=1;j<=i;j++)
if(j*2<=i) (ans+=F1[i][j])%=mod;
ans++;
}else{
int x = G[0],y = G[1];
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;
}
return ans;
}
signed main(){
int t;
cin>>t;
for(int i = 1;i<=t;i++){
printf("Case %lld: %lld\n",i,solve());
}
return 0;
}