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

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

zoj 2315 New Year Bonus Grant

系統(tǒng) 1908 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


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

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

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

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

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

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

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 五月婷婷天 | 国产美女做爰免费视 | 欧美成人性色生活片天天看 | 欧美日韩亚洲国产精品一区二区 | 久久九九亚洲精品 | a毛片在线观看 | 亚洲国产一区二区三区 | 国产精品四虎 | 国产成+人+综合+亚洲 欧美 | 久久久精品久久视频只有精品 | 亚洲无限看 | 国产美女亚洲精品久久久久久 | 日本在线有码 | 国产福利一区二区精品视频 | 国产高清福利91成人 | 99国产精品免费视频观看 | 视频福利一区 | 13一14周岁毛片免费 | 99热综合在线 | 亚洲另在线日韩综合色 | 四虎在线最新永久免费播放 | 亚洲精品中文一区不卡 | 日本aa在线 | 久 在线播放 | 四虎国产精品免费视 | 成年女人在线观看 | 日韩欧免费一区二区三区 | 成人午夜大片免费7777 | 国产91福利在线精品剧情尤物 | 操你妹影院 | 在线观看a视频 | 99爱精品视频 | 日本一区二区三区四区在线观看 | 天天做人人爱夜夜爽2020 | 2022国产91精品久久久久久 | 深夜福利院 | 色综合网站国产麻豆 | 第一福利在线观看 | 99精品视频在线观看免费专区 | 国产精品全国探花泡良大师 | 亚洲精品色播一区二区 |