可爱的传送门酱在这里

题意:给你一棵最多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)

分类: 文章

quhengyi11

喵(ฅ>ω<*ฅ)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *