题意：给你一棵最多 200 个点的树，求有多少个子联通块能使得它的重心和原来的树重合（如果原来的树有两个重心，那么子联通块也要有两个重心），共 50 组 case。
方法一：枚举，暴力，我会求重心
正解：一个点是树的重心，当且仅当它为根的时候，所有子节点为根的树的大小都小于等于总点数的一半，我们可以将相同重心的子树计数转换为满足这个性质的计数，当有两个根的时候，两个重心一定相邻，我们在它之间加一个点，两个重心都连向这个点并删除两重心之间的边，这样这个新点就是树的唯一一个重心了，最后统计答案的时候减掉一个就行。
这个时候我们得到了一棵有根树，需要求有多少个以原来的根为根的子树，去掉这个根后其它的联通块大小小于等于子树大小的一半。
因为这个是在根上的计数，我们不妨先把除根以外其它点为根时候的方案数算算
令 $f[u][i]$表示以 u 为根的子树有 i 个节点时候的方案数。
我们有：$f[u][i+j]+=f[u][i]\times f[v][j](v \in son[u])$
其中 i 是当前子树 u 的 size，j 是子树 v 的 size(这个会树形 dp 的应该都很熟悉了)
此刻我们已经完成了对 i 的计数，
我们再对根 (用 rt 表示) 进行计数，因为有子树大小不超过总结点数一半的约束条件 (子树指的是以 rt 的儿子为根的子树)，我们需要在 dp 的时候就把这个约束设进去，因此我们假设 $g[i][j][k]$表示枚举到 rt 的第 i 个儿子时，子树最大是 j 个结点，总共有 k 个结点时候的方案数。于是我们开始闷声写方程
$g[i][j][k+l]+=g[i-1][j][k]*f[son[i]][l]$
这里 l 是枚举第 i 个儿子大小，k 是枚举前面子树的大小的，因此显然有 $l<=j$，而我们的 i 枚举的是根的儿子结点，在菊花图的时候也是 n 的复杂度，j 枚举的大小肯定是最大子树的大小，这样想想就 $O(n^4)$的复杂度了不就打出 gg 了吗？
我们可以将儿子结点按它们子树的大小从小到大排序，这样每次 j 就只需要枚举到当前子树的大小即可，相应的方程要改一改（具体看代码）。听说这样就能优化到 $O(n^3)$，然而我真的不会证复杂度（
#include<bits/stdc++.h>
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 205
#define Re register
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 10007
int n, T, head[N], tot, u, v;
struct edge{
int nxt, v;
}e[N << 1];
int f[N][N], g[N][N][N];//f[i][j] 表示 i 点为根的有 j 个节点的联通块有多少点，g[i][j][k] 表示根的第 i 个儿子，最大的儿子有不超过 j 个节点，共 k 个节点的方案数，最后的时候用补集转换一下就能得到最大儿子有 j 个节点的方案数。
inline void addedge (int u, int v)
{
e[++tot] = (edge) {head[u], v};
head[u] = tot;
}
int sz[N], max[N];
inline void dfs (int u, int fa)
{
sz[u] = 1;
edge (i, u)
{
if (v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
max[u] = std::max(max[u], sz[v]);
}
max[u] = std::max(n - sz[u], max[u]);
}
int rt1, rt2, rt, mn, ans;
inline void findroot ()
{
mn = inf;
fo (i, 1, n) mn = std::min(mn, max[i]);
rt1 = rt2 = rt = 0;
fo (i, 1, n)
if (mn == max[i])
{
if (!rt1)
rt1 = i;
else
rt2 = i;
}
if (!rt2)
{
rt = rt1;
ans = 1;//重心单独一个联通块
}
else
{
rt = ++n;//建立虚根？（其实就是让重心为 1 个）
edge (i, rt1)
if (v == rt2)
{
e[i].v = rt;
break;
}
edge (i, rt2)
if (v == rt1)
{
e[i].v = rt;
break;
}
addedge(rt, rt1);
addedge(rt, rt2);
}
}
int h[N];
inline void treedp (int u, int fa)
{
sz[u] = 1;//记得重新计算 u 点 sz 喵
f[u][0] = f[u][1] = 1;
edge (qwq, u)
{
if (v == fa) continue;
treedp(v, u);
memset(h, 0, sizeof h);
fo (i, 1, sz[u])
fo (j, 1, sz[v])
h[i + j] = (h[i + j] + f[u][i] * f[v][j]) % mod;
sz[u] += sz[v];
fo (i, 1, sz[u]) f[u][i] = (f[u][i] + h[i]) % mod;
}
}
int son[N], cnt, sum;
inline void init ()
{
ans = 0;
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
memset(max, 0, sizeof max);
tot = 0;
cnt = 0;
memset(head, 0, sizeof head);
}
inline bool cmp (int x, int y)
{
return sz[x] < sz[y];
}
int main()
{
scanf("%d", &T);
fo (QvQ, 1, T)
{
scanf("%d", &n);
init();
fo (i, 2, n)
{
scanf("%d %d", &u, &v);
addedge(u, v);
addedge(v, u);
}
dfs(1, 0);
findroot();
treedp(rt, 0);
edge (i, rt)
son[++cnt] = v;
std::sort(son + 1, son + cnt + 1, cmp);
sum = 0;
fo (i, 0, 200) g[0][i][0] = g[0][i][1] = 1;
fo (i, 1, cnt)
{
fo (j, 1, sz[son[i]])
fo (k, 0, sum)
fo (l, 0, j)
{
g[i][j][k + l] = (g[i][j][k + l] + g[i - 1][std::min(j, sz[son[i - 1]])][k] * f[son[i]][l]) % mod;
}
sum += sz[son[i]];
}
fo (i, 1, sz[son[cnt]])
fo (j, i << 1, n)
ans = (ans + g[cnt][i][j] - g[cnt][i - 1][j]) % mod;
printf("Case %d: %d\n", QvQ, (ans + mod) % mod);
}
return 0;
}
参考资料：Bill Yang's blog
(讲真我觉得我的思路到 g 函数那里都是靠 Bill Yang 学长的 blog 的自己姿势水平太低了 QAQ)
0 条评论