#include#include#include#include#include#include#include#include#include

欧美三区_成人在线免费观看视频_欧美极品少妇xxxxⅹ免费视频_a级毛片免费播放_鲁一鲁中文字幕久久_亚洲一级特黄

zoj 2315 New Year Bonus Grant

系統 1700 0

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1315

簡單的樹型DP ??

代碼:

      #include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<stack>

#include<queue>

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

#define ll long long



using namespace std;

const int INF=0x3f3f3f3f;

const int MOD=100000007;

const int N=500005;

int MAX[N][2],f[N];

int in[N],c[N];

int head[N],I;

vector<int>vt;

struct node

{

    int j,next;

}edge[N];

void add(int i,int j)

{

    edge[I].j=j;

    edge[I].next=head[i];

    head[i]=I++;

}

int dp(int x,int k)

{

    if(MAX[x][k]!=-1)

    return MAX[x][k];

    if(in[x]==0)

    return (MAX[x][k]=0);

    MAX[x][k]=0;

    int tmp=-INF,l=0;

    for(int t=head[x];t!=-1;t=edge[t].next)

    {

        int w=edge[t].j;

        MAX[x][k]+=(dp(w,0));

        if(dp(w,1)-dp(w,0)>tmp)

        {

            tmp=dp(w,1)-dp(w,0);

            l=w;

        }

    }

    if(k==0)

    {

        c[x]=l;

        MAX[x][k]+=(tmp+1);

    }

    return MAX[x][k];

}

void dfs(int x,int k)

{//cout<<x<<" "<<k<<endl;

    if(in[x]==0) return;

    if(k==0)

    vt.push_back(c[x]);

    for(int t=head[x];t!=-1;t=edge[t].next)

    {

        int w=edge[t].j;

        if(k==0&&c[x]==w)

        dfs(w,1);

        else

        dfs(w,0);

    }

}

int main()

{

    //freopen("data.in","r",stdin);

    int T;

    cin>>T;

    while(T--)

    {

        int n;

        cin>>n;

        memset(in,0,sizeof(in));

        memset(head,-1,sizeof(head));I=0;

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

        {cin>>f[i];++in[f[i]];add(f[i],i);}

        memset(MAX,-1,sizeof(MAX));

        cout<<(dp(1,0)*1000)<<endl;

        vt.clear();

        dfs(1,0);

        sort(vt.begin(),vt.end());

        for(unsigned int i=0;i<vt.size();++i)

        {

            if(i>0) cout<<" ";

            cout<<vt[i];

        }cout<<endl;

    }

    return 0;

}


    

zoj 2315 New Year Bonus Grant


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 亚洲人人精品 | 新版天堂资源中文在线 | 欧美一区二区三区大片 | 亚洲色色| 国产一级高清 | 成人精品一区二区三区 | 欧美黑人ⅹxxx片 | 夜夜艹日日艹 | 亚洲精品乱码久久久久久花季 | 欧美人xx| 免费播放欧美一级特黄 | 99pao成人国产永久免费视频 | 国产噜噜噜精品免费 | 久久高清免费视频 | 国产se| 男人的天堂在线视频 | 国产精品三级在线播放 | 午夜国产| 国产成人手机在线好好热 | jdav视频在线观看免费 | 一级片观看 | 午夜久草 | 天天鲁天天爽天天视频 | 中文字幕日韩在线 | 国产精品久久久一区二区三区 | 2017最新h无码动漫 | 那里有毛片看 | 日韩在线 在线播放 | 毛片毛片毛片毛片毛片 | 在线免费日韩 | 日韩色区 | 开心网五月色婷婷综合图片 | 成人毛片视频在线观看 | 99在线免费观看 | 三级精品在线观看 | 91.成人天堂一区 | 一级美女大片 | 小明免费视频一区二区 | 日韩欧美亚洲国产 | jzz 护士| 高清一区二区三区四区五区 |