VIJOS:P1706（舞会）

描述

Arthur公司是一个等级森严的公司，它们有着严格的上司与下属的关系，公司以总裁为最高职位，他有若干个下属，他的下属又有若干个下属，他的下属的下属又有若干个下属……现接近年尾，公司组织团拜活动，活动中有一部分是自由舞会，公司的每个职员都有一个搞笑值，现要你制定一套哪些人上台的方案，使得台上所有演员的搞笑值最大。当然，职员们是不会和他们的顶头上司一起上台的。

格式

输入格式

第一行一个整数N，表示这个公司总共的职员个数。

接下来一行有N个整数，由空格隔开，第i个整数表示职员i的搞笑值Ai（-1327670≤Ai≤1327670）。

接下来N-1行，每行一个1到N的整数，第i个整数表示职员i+1的顶头上司是谁，当然总裁就是职员1。

输出格式

一个整数，表示台上所有职员搞笑值之和的最大值。

输入：

7
1 1 1 1 1 1 1
1
1
5
1
4
4

输出：

没有上司的舞会问题

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

const int MAXN=;

typedef long long ll;

int n;

int v[MAXN];

vector<int> tree[MAXN];

ll dp[MAXN][];

void dfs(int u)

{

    dp[u][]+=v[u];

    for(int i=;i<tree[u].size();i++)

    {

        int v=tree[u][i];

        dfs(v);

        dp[u][]+=max(dp[v][],dp[v][]);

        dp[u][]+=dp[v][];

    }

}

int main()

{

    cin>>n;

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

    {

        cin>>v[i];

    }

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

    {

        int fa;

        cin>>fa;

        tree[fa].push_back(i);

    }

    dfs();

    cout<<max(dp[][],dp[][])<<endl;

    return ;

}

巴特西

VIJOS:P1706（舞会）

描述

格式

输入格式

输出格式

最新文章

热门文章