树形dp HDU6867 Tree-蒲公英云

树形dp HDU6867 Tree

男娘i 2022-11-29 03:03 257阅读 0赞

题目链接

多校，怎么越来越难了，是我变菜了吗。

不多说，这是一道树形dp的题目，AC代码如下。

AC代码

#include <cstdio>
using namespace std;
const int max_n=500000;
int n,tot;
long long ans;
int v[max_n+1],nxt[max_n+1],h[max_n+1],dep[max_n+1],siz[max_n+1];
// 其实我一般不写快读，这里参考一下，留一个模板。
// 万一哪次用到了呢
int readint()
{
    int x=0,f=1;
    char ch=getchar();
    // 判断是否负数
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    // 读入数字
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    // 一定要返回带符号的数字
    return x*f;
}
void init()
{
    for(int i=1;i<=n;++i)
    {
        h[i]=0;
    }
    tot=0;
    ans=0;
    dep[1]=0;
}
void dfs1(int u)
{
    siz[u]=1;
    for(int p=h[u];p;p=nxt[p])
    {
        dep[v[p]]=dep[u]+1;
        dfs1(v[p]);
        siz[u]+=siz[v[p]];
    }
}
template<typename T> bool chkmax(T &x,T y)
{
    if(x<y)
    {
        x=y;
        return true;
    }
    return false;
}
void dfs2(int u,long long k)
{
    // 预定义了一个这样的东西
    chkmax(ans,k);
    for(int p=h[u];p;p=nxt[p])
    {
        dfs2(v[p],k+n-siz[v[p]]);
    }
}
int main()
{
    int T=readint();
    while(T--)
    {
        n=readint();
        init();
        // 读入树
        for(int i=2;i<=n;++i)
        {
            int k=readint();
            v[++tot]=i;
            nxt[tot]=h[k];
            h[k]=tot;
        }
        dfs1(1);
        dfs2(1,0);
        for(int i=1;i<=n;++i)
        {
            ans+=siz[i];
        }
        printf("%lld\n",ans);
    }
    return 0;
}