HDU 4863 Centroid of a Tree

树的重心，树形$dp$，背包。

树的重心有两个充分必要条件：

$1$.某树有两个重心$a$，$b$ $<=>$ $a$与$b$相邻，断开$a$与$b$之间的边之后，两个联通分量内的点的个数相同。

$2$.某树有一个重心$a$ $<=>$ 以$a$为根的树，去掉a之后，剩下的联通分量，除去节点个数最多的联通分量后，剩余的联通分量节点个数之和大于等于最大的联通分量的节点个数。

因此，可以先计算出初始树的重心，分两种情况讨论。

如果有两个重心$a$，$b$，那么，我们需要计算出断开$a$,$b$之间的边，以$a$为根的树以及以$b$为根的树中包含$x$个节点的树有几种，然后枚举$x$两边相乘求和就是答案了。

如果只有一个重心$a$，这种情况比两个重心的复杂一点，需要计算以$a$为根的树有多少种满足充要条件$2$，先要计算出以$a$的儿子为根的树中包含$x$个节点的树有几种，然后再用背包去算一下反面的情况，总的方案减去反面的就是答案。

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<ctime>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0);

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

template <class T>

inline void read(T &x)

{

    char c = getchar();

    x = ;

    while(!isdigit(c)) c = getchar();

    while(isdigit(c))

    {

        x = x *  + c - '';

        c = getchar();

    }

}

int T,n;

int mod=;

int dp[][];

int c[],mx[],k[],f[];

vector<int>tmp[],t[],zx;

void init()

{

    memset(dp,,sizeof dp);

    memset(c,,sizeof c);

    memset(mx,,sizeof mx);

    memset(f,,sizeof f);

    for(int i=;i<=n;i++) tmp[i].clear();

    for(int i=;i<=n;i++) t[i].clear();

    zx.clear();

}

void D(int x)

{

    f[x]=;

    for(int i=;i<tmp[x].size();i++)

    {

        if(f[tmp[x][i]]) continue;

        t[x].push_back(tmp[x][i]);

        D(tmp[x][i]);

    }

}

void F(int x)

{

    for(int i=;i<t[x].size();i++)

    {

        F(t[x][i]);

        mx[x]=max(mx[x],c[t[x][i]]);

        c[x]=c[x]+c[t[x][i]];

    }

    c[x]++;

}

void G(int x)

{

    f[x]=;

    for(int i=;i<tmp[x].size();i++)

    {

        if(f[tmp[x][i]]) continue;

        if(zx.size()==&&tmp[x][i]==zx[]) continue;

        t[x].push_back(tmp[x][i]);

        G(tmp[x][i]);

    }

}

void DP(int x)

{

    dp[x][]=; int h[],g[];

    memset(h,,sizeof h); memset(g,,sizeof g);

    g[]=;

    for(int i=;i<t[x].size();i++)

    {

        DP(t[x][i]);

        for(int j=;j<=c[x]+c[t[x][i]];j++) h[j]=;

        for(int p1=c[x];p1>=;p1--)

            for(int p2=c[t[x][i]];p2>=;p2--)

                h[p1+p2]=(h[p1+p2]+g[p1]*dp[t[x][i]][p2]%mod)%mod;

        for(int j=;j<=c[x]+c[t[x][i]];j++) g[j]=h[j];

        c[x]=c[x]+c[t[x][i]];

    }

    c[x]++;

    for(int i=;i<=;i++) dp[x][i]=g[i-];

}

int main()

{

    scanf("%d",&T); int cas=;

    while(T--)

    {

        scanf("%d",&n);

        init();

        for(int i=;i<=n-;i++)

        {

            int x,y; scanf("%d%d",&x,&y);

            tmp[x].push_back(y);

            tmp[y].push_back(x);

        }

        D(); F();

        for(int i=;i<=n;i++) k[i]=max(mx[i],n-c[i]);

        int mn=; for(int i=;i<=n;i++) mn=min(mn,k[i]);

        for(int i=;i<=n;i++) if(k[i]==mn) zx.push_back(i);

        for(int i=;i<=n;i++) t[i].clear();

        memset(f,,sizeof f);

        G(zx[]); if(zx.size()==) G(zx[]);

        memset(c,,sizeof c);

        DP(zx[]); if(zx.size()==) DP(zx[]);

        printf("Case %d: ",cas++);

        int ans=;

        if(zx.size()==)

        {

            int h[],g[]; int fm=;

            for(int i=;i<t[zx[]].size();i++)

            {

                memset(h,,sizeof h); memset(g,,sizeof g); g[]=;

                int a=;

                for(int j=;j<t[zx[]].size();j++)

                {

                    if(i==j) continue;

                    for(int w=;w<=a+c[t[zx[]][j]];w++) h[w]=;

                    for(int p1=a;p1>=;p1--)

                        for(int p2=c[t[zx[]][j]];p2>=;p2--)

                            h[p1+p2]=(h[p1+p2]+g[p1]*dp[t[zx[]][j]][p2]%mod)%mod;

                    a=a+c[t[zx[]][j]];

                    for(int j=;j<=;j++) g[j]=h[j];

                }

                for(int j=;j<=c[t[zx[]][i]];j++)

                    for(int w=;w<j;w++)

                        fm=(fm+dp[t[zx[]][i]][j]*g[w]%mod)%mod;

            }

            for(int i=;i<=n;i++) ans=(ans+dp[zx[]][i])%mod;

            printf("%d\n",(ans-fm+mod)%mod);

        }

        else

        {

            for(int i=;i<=;i++)

                ans=(ans+dp[zx[]][i]*dp[zx[]][i]%mod)%mod;

                printf("%d\n",ans);

        }

    }

    return ;

}

巴特西

HDU 4863 Centroid of a Tree

最新文章

热门文章