树形dp HDU6867 Tree

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

[题目链接][Link 1]

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

不多说，这是一道树形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;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6867