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

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

zoj 2315 New Year Bonus Grant

系統(tǒng) 1959 0

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

簡(jiǎn)單的樹(shù)型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


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號(hào)聯(lián)系: 360901061

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

【本文對(duì)您有幫助就好】

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長(zhǎng)會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 日本免费黄色小视频 | 久久久免费网站 | 中文字幕在线不卡视频 | 国产综合精品一区二区 | 久久久久久亚洲精品不卡 | 九九久久久久久久爱 | 女人18一级毛片免费观看 | 色综合亚洲欧美在线 | 曰本女人一级毛片看一级毛 | 最新久久免费视频 | 国产福利在线观看第二区 | 亚洲成人免费在线 | 国产日韩精品视频一区二区三区 | 日日摸夜夜夜夜夜添 | 伊人久久精品线影院 | 99在线热视频 | 久久99精品久久久久久噜噜 | 国产日产久久 | 天天爽夜夜爽天天做夜夜做 | 亚洲精品一二三四 | 97国产成人精品免费视频 | 久久国产亚洲精品 | 91精品国产一区二区三区左线 | 可以免费观看的一级毛片 | 久久99精品亚洲热综合 | 国产精品一区二区三 | 日韩性网| 成人日韩视频 | 国产亚洲久久 | 久久久久久9 | 亚洲va欧美va国产va天堂影 | 五月综合在线 | 国产三级做爰高清视频a | 国产成人亚洲精品无广告 | 亚洲欧美一区二区三区不卡 | 国产精品夜色7777青苹果 | 久久高清精品 | 亚洲日本va| 狠狠色丁香婷婷综合小时婷婷 | 国产免费一区二区在线看 | 奇米影视777狠狠狠888不卡 |