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

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

zoj 2315 New Year Bonus Grant

系統 1617 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條評論
主站蜘蛛池模板: 久久中文在线 | 在线观看福利网站 | 中文有码第一页 | 国产综合视频 | 婷婷色吧 | 一区二区精品在线观看 | 国产在线视频你懂得 | 青青草久热精品视频在线观看 | 久久桃花综合 | 奇米网久久 | 超清中文乱码精品字幕在线观看 | 国内精品自在自线香蕉 | 爱久久www.35669 | 免费一级毛片 | 97高清国语自产拍免费 | 久久国产99 | 中国精品久久精品三级 | 久青草免费在线视频 | 亚洲综合在线观看视频 | 亚洲综合日韩中文字幕v在线 | 四虎影院永久网站 | 欧美一区二区在线观看视频 | 国产精品美女视频 | 国产色a在线观看 | 久久青青草原精品国产麻豆 | 亚洲精品久久99久久 | 日韩视频精品 | 九七97影院理论片手机在线观看 | 免费在线观看黄色毛片 | 久草视频播放器 | 成人在激情在线视频 | 欧美性猛交xxxx免费看手交 | 精品无码久久久久久久动漫 | 国产一区二区三区在线观看视频 | 色中色资源站 | 亚洲综合第一欧美日韩中文 | 99精品欧美一区二区三区 | 国产成人久久精品推最新 | 国产亚洲精品线观看77 | 大毛片a大毛片 | 日本人成18在线播放 |