首页 > 试题广场 >

派对的最大快乐值

[编程题]派对的最大快乐值
  • 热度指数:4037 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
整个公司的人员结构可以看作是一棵标准的多叉树。树的头节点是公司唯一的老板,除老板外,每个员工都有唯一的直接上级,叶节点是没有任何下属的基层员工,除基层员工外,每个员工都有一个或多个直接下级,另外每个员工都有一个快乐值。
这个公司现在要办 party,你可以决定哪些员工来,哪些员工不来。但是要遵循如下的原则:
1.如果某个员工来了,那么这个员工的所有直接下级都不能来。
2.派对的整体快乐值是所有到场员工快乐值的累加。
3.你的目标是让派对的整体快乐值尽量大。
给定一棵多叉树,请输出派对的最大快乐值。

输入描述:
第一行两个整数 n 和 root,n 表示公司的总人数,root 表示公司的老板。

第二行 n 个整数 happy_i 表示员工 i 的快乐值。

接下来 n - 1 行每行两个整数 u_i 和 v_i 表示 u_i 是 v_i 的直接上级。


输出描述:
输出一个整数表示最大快乐值。
示例1

输入

3 1
5 1 1
1 2
1 3

输出

5

备注:

输入保证是一棵树
#include <bits/stdc++.h>
using namespace std;

int T[500003];
unordered_map<int, vector<int>> V;

struct P{
    int x, y;
};

P DFS(int k){
    P p = P{T[k], 0};
    for(auto &v: V[k]){
        P t = DFS(v);
        p.x += t.y;
        p.y += max(t.x, t.y);
    }
    return p;
}

int main(){
    int n, r, u, v;
    scanf("%d%d", &n, &r);
    for(int i=1;i<=n;i++)
        scanf("%d", &T[i]);
    for(int i=1;i<n;i++){
        scanf("%d%d", &u, &v);
        V[u].push_back(v);
    }
    P p = DFS(r);
    printf("%d\n", max(p.x, p.y));
    return 0;
}

编辑于 2020-05-28 02:18:57 回复(0)
树型DP,建立多叉树,然后父节点分为来与不来两种情况往子节点要信息(子节点来时的最大快乐值,子节点不来时的最大快乐值),然后构成自己的信息返回给上一级使用。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.HashMap;
import java.util.Iterator;

class Employee {
    public int happy;
    public LinkedList<Employee> subordinates;
    public Employee(int happy) {
        this.happy = happy;
        subordinates = new LinkedList<>();
    }
}

class Info {
    public int come;         // 来产生的快乐值
    public int notCome;      // 不来产生的快乐值
    public Info(int come, int notCome){
        this.come = come;
        this.notCome = notCome;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), bossId = Integer.parseInt(params[1]);
        int[] happy = new int[n];
        params = br.readLine().split(" ");
        for(int i = 0; i < n; i++) happy[i] = Integer.parseInt(params[i]);
        // 哈希表构建多叉树
        HashMap<Integer, Employee> map = new HashMap<>();
        Employee boss = new Employee(happy[bossId - 1]);
        map.put(bossId, boss);
        String line;
        while((line = br.readLine()) != null){
            params = line.split(" ");
            int idb = Integer.parseInt(params[0]), ids = Integer.parseInt(params[1]);
            Employee p = map.get(idb), c = new Employee(happy[ids - 1]);
            p.subordinates.add(c);
            map.put(ids, c);
        }
        // 树型DP
        Info info = process(boss);
        System.out.println(Math.max(info.notCome, info.come));
    }
    
    private static Info process(Employee e) {
        if(e.subordinates.isEmpty()) return new Info(e.happy, 0);
        int comeHappy = e.happy, notComeHappy = 0;
        Iterator<Employee> iter = e.subordinates.iterator();
        while(iter.hasNext()){
            Info info = process(iter.next());
            comeHappy += info.notCome;      // 如果我来,那我的部下就不能来
            notComeHappy += Math.max(info.come, info.notCome);      // 如果我不来,我的部下来不来都行,取大的那个
        }
        return new Info(comeHappy, notComeHappy);
    }
}

发表于 2021-11-18 16:48:46 回复(0)
import java.util.*;
import java.io.*;

//dfs + dp
public class Main {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int boss = sc.nextInt()-1;
        int[][] dp = new int[n][2];
        int[] score = new int[n];
        ArrayList<ArrayList<Integer>> adjaMatrix = new ArrayList<ArrayList<Integer>>(n);

        for (int i = 0; i < n; i++) {
            dp[i][0] = -1; dp[i][1] = -1;
        }

        for (int i = 0; i < n; i++) {
            score[i] = sc.nextInt();
            adjaMatrix.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < n - 1; i++) {
            adjaMatrix.get(sc.nextInt()-1).add(sc.nextInt()-1);
        }

        dfs(adjaMatrix, score, dp, boss);
        System.out.printf("%d\n", Math.max(dp[boss][1], dp[boss][0]));

        sc.close();
    }

    public static void dfs(ArrayList<ArrayList<Integer>> adjaMatrix, int[] score, int[][] dp, int i) {
        if (dp[i][0] != -1) {
            return ;
        }

        dp[i][0] = 0;
        dp[i][1] = score[i];

        for (int j = 0; j < adjaMatrix.get(i).size(); j++) {
            dfs(adjaMatrix, score, dp, adjaMatrix.get(i).get(j));

            dp[i][1] += dp[adjaMatrix.get(i).get(j)][0];
            dp[i][0] += Math.max(dp[adjaMatrix.get(i).get(j)][0], dp[adjaMatrix.get(i).get(j)][1]);
        }
    }
}


发表于 2020-07-23 00:22:55 回复(0)
#include <iostream>
#include <vector>
#include <algorithm>

struct Node{
    int happy = 0;
    int parent = -1;
    std::vector<int> child;
    int subTreeMaxHappy = 0;//以本节点为根的子树,不带父节点的最大快乐值
};

int calcSubTreeMaxHappy(std::vector<Node> &inputs, int index)
{
    auto &node = inputs[index];
    if (node.child.empty())
        return node.happy;
    if (node.subTreeMaxHappy != 0)
        return node.subTreeMaxHappy;
    //分本节点去和本节点不去2种情况
    //分别计算2种情况值,取最大值
    int total1 = node.happy, total2 = 0;
    //本节点去
    for (int i = 0; i < node.child.size(); ++i) {
        auto &childIndex = node.child[i];
        for (int j = 0; j < inputs[childIndex].child.size(); ++j) {
            total1 += calcSubTreeMaxHappy(inputs, inputs[childIndex].child[j]);
        }
    }
    //本节点不去
    for (int i = 0; i < node.child.size(); ++i) {
        total2 += calcSubTreeMaxHappy(inputs, node.child[i]);
    }
    node.subTreeMaxHappy = std::max(total1, total2);
    return node.subTreeMaxHappy;
}

int main()
{
    int n, root;
    std::vector<Node> inputs;
    Node node;
    std::cin >> n >> root;
    inputs.resize(n+1);
    for (int i = 1; i < n+1; ++i) {
        std::cin >> inputs[i].happy;
    }
    int a, b;
    for (int i = 0; i < n - 1; ++i) {
        std::cin >> a >> b;
        inputs[b].parent = a;
        inputs[a].child.emplace_back(b);
    }
    std::cout<<calcSubTreeMaxHappy(inputs, root)<<std::endl;
}
发表于 2019-09-02 11:10:59 回复(0)

使用邻接矩阵建图之后,dfs即可。

树形dp,状态表示:

  • dp[i][0]表示i不去,他及他的所有下属能获得的最大快乐值
  • dp[i][1]表示i去的情况下,他及他的下属能获得的最大快乐值

则结果为:max(dp[root][0], dp[root][1])

状态转移:

  • dp[i][0] = i的所有直接下属j的max(dp[j][0], dp[j][1])之和
  • dp[i][1] = i的所有直接下属j的dp[j][0]之和 + happy[i]

code:

#include 
#include 
#include 
using namespace std;
int idx;

// 建图,h记录头节点,ne记录结点的下一个结点的位置,e记录结点的值
// 遍历时,从h中找到i结点对应的下标,则ne[i]是i结点的子结点,知道ne[i]==-1
void add(int a, int b, vector& h, vector& e, vector& ne) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs (int u, vector& happy, vector& h, vector& e, vector& ne, vector>& dp) {
    // 此人去的话,快乐值至少为他自己的快乐值
    dp[u][1] = happy[u];
    // 遍历所有他的下属
    for (int i = h[u]; i != -1; i = ne[i]) {
        // 对于下属j,求j去的最大快乐值和j不去的最大快乐值
        int j = e[i];
        dfs(j, happy, h, e, ne, dp);

        // u去的话,只能加上j不去时的快乐值
        dp[u][1] += dp[j][0];
        // u不去的话,快乐值最大为j去与不去中的最大值
        dp[u][0] += max(dp[j][0], dp[j][1]);
    }
}
int main()
{
    cin.tie();
    ios::sync_with_stdio(false);

    int n, root;
    cin >> n >> root;

    int N = n + 1;
    vector h(N, -1);
    vector e(N);
    vector ne(N);
    vector happy(N);
    vector> dp(N, vector(2, 0));

    for (int i = 1; i > happy[i];
    for (int i = 0; i < n - 1; i++) {
        // 建图
        int a, b;
        cin >> a >> b;
        add(a, b, h, e, ne);
    }

    dfs(root, happy, h, e, ne, dp);

    cout << max(dp[root][0], dp[root][1]) << endl;

    return 0;
}
发表于 2020-01-01 14:54:23 回复(0)
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

//缓存参加与不参加时子树的最大快乐数结果
int *happy_max0;
int *happy_max1;

struct deployee {
    int happy;
    int id;
    struct deployee *par;    //上级
    struct deployee *son;    //下级
    struct deployee *bro;    //兄弟
};

int findMaxHappy(struct deployee *par, int come) {
    int max = 0;
    int sonMax1, sonMax2;
    //先查缓存
    if (come && happy_max1[par->id] >= 0)
        return happy_max1[par->id];
    if (!come && happy_max0[par->id] >= 0)
        return happy_max0[par->id];
    struct deployee *bro;
    if (come) {
        //根节点参加但无子节点时
        if (!par->son)
            return par->happy;
        max += par->happy;
        bro = par->son;
        //递归求解子节点不参加时子树的最大快乐数并缓存
        while(bro) {
            happy_max0[bro->id] = findMaxHappy(bro, 0);
            max += happy_max0[bro->id];
            bro = bro->bro;
        }
    }
    else {
        //根节点不参加且没子节点时
        if (!par->son)
            return 0;
        bro = par->son;
        //递归求解子节点不参加或不参加时子树的最大快乐数,缓存并取最大值
        while(bro) {
            happy_max1[bro->id] = findMaxHappy(bro, 1);
            happy_max0[bro->id] = findMaxHappy(bro, 0);
            if (happy_max1[bro->id] >= happy_max0[bro->id])
                max += happy_max1[bro->id];
            else
                max += happy_max0[bro->id];
            bro = bro->bro;
        }
    }
    return max;
}

int main() {
    int n, root;
    int a, b;
    int x, y;
    struct deployee *deps;
    
    scanf("%d %d", &n, &root);
    happy_max0 = (int *)malloc(sizeof(int) * n);
    memset(happy_max0, -1, sizeof(int) * n);
    happy_max1 = (int *)malloc(sizeof(int) * n);
    memset(happy_max1, -1, sizeof(int) * n);

    deps = (struct deployee *)malloc(sizeof(struct deployee) * n);
    memset(deps, 0, sizeof(struct deployee) * n);
    for (int i = 0; i < n; i++) {
        deps[i].id = i;
        if (i < n - 1)
            scanf("%d ", &deps[i].happy);
        else
            scanf("%d",  &deps[i].happy);
    }
    
    for (int i = 0; i < n - 1; i++) {
        scanf("%d %d", &x, &y);
        x--;
        y--;
        deps[y].par = &deps[x];
        deps[y].bro = deps[x].son;
        deps[x].son = &deps[y];
    }
    
    a = findMaxHappy(&deps[root - 1], 0);
    b = findMaxHappy(&deps[root - 1], 1);
    
    if (a >= b)
        printf("%d\n", a);
    else
        printf("%d\n", b);
    return 0;
}

编辑于 2019-12-05 02:02:06 回复(0)
只有我不会建树吗。。

发表于 2022-06-15 17:20:20 回复(0)
老老实实建树,搜索。。
#include<bits/stdc++.h>
using namespace std;
class TreeNode{
    public:
    int happy;
    vector<TreeNode*> children;
    TreeNode(int h):happy(h){};
};
unordered_map<TreeNode*,int> mp;
int getMax(TreeNode* root){
    if(mp.count(root))return mp[root];
    int res0=0,res1=0;
    for(auto r:root->children){
        res0+=getMax(r);
        for(auto rr:r->children){
            res1+=getMax(rr);
        }
    }
    int re***ax(res0,res1+root->happy);
    mp[root]=res;
    return res;
}
int main(){
    int n,root;
    cin>>n>>root;
    vector<TreeNode*> happy(n);
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        happy[i]=new TreeNode(t);
    }
    for(int i=0;i<n-1;i++){
        int ui,vi;
        scanf("%d%d",&ui,&vi);
        happy[ui-1]->children.push_back(happy[vi-1]);
    }
    cout<<getMax(happy[root-1])<<endl;
    return 0;
}


发表于 2019-11-30 11:31:17 回复(0)
//树形DP
#include <iostream>
#include <list>
#include <vector>
using namespace std;
class Employee{
public:
    int happy;
    vector<Employee*> sub;
    Employee(int h):happy(h){}
    
};
class returnData{
public:
    int yesMax;
    int noMax;
    returnData(int yes,int no):yesMax(yes),noMax(no)
    {}
};
returnData process(Employee* x) {
    int yesX = x -> happy;
    int noX = 0;
    if(x -> sub.size() == 0) {
        return returnData(yesX,noX);
    }
    else {
        for (auto next : x -> sub) {
            returnData subTree = process(next);
            yesX += subTree.noMax;
            noX += max(subTree.noMax,subTree.yesMax);
        }
    }
    return returnData(yesX,noX);
}
int getMaxHappy(Employee* boss) {
    returnData allTreeinfo =  process(boss);
    return max(allTreeinfo.yesMax,allTreeinfo.noMax);
}
int main() {
    int n,root;
    cin >> n >> root;
    vector<Employee*> happy(n);
    int t;
    for(int i = 0;i < n;++i){
        cin >> t;
        happy[i] = new Employee(t);
    }
    int u,v;
    for(int i = 1;i < n;++i){
        cin >> u >> v;
        happy[u-1]->sub.push_back(happy[v-1]);
    }
    auto x= getMaxHappy(happy[root-1]);
    cout << x << endl;
    return 0;
}

发表于 2023-04-19 15:08:18 回复(0)
import sys
data = []
for line in sys.stdin:
    data.append(line.split())  # 每一行的输入
n = 0 # 公司总人数
happyValue = {}
tree = {}  # 存储每个员工的直接上下级关系
root = 0  # 根节点,老板的编号
for i, value in enumerate(data):
    if i == 0:
        n = int(value[0])
        root = int(value[1])
    elif i == 1:
        for j, happy in enumerate(value):
            happyValue[j+1] = int(happy)
    else:
            if int(value[0]) not in tree:
                tree[int(value[0])] = [int(value[1])]
            else:
                tree[int(value[0])].append(int(value[1]))    
def process(root):  # 从根节点开始,输出以root为上级的最大快乐值,root来的时候最大快乐值以及root不来的时候的最大快乐值
    if root not in tree:  # basecase:当前节点没有下级
      return [happyValue[root], 0]  # 来的时候为自己的快乐值,不来为0
    includeRoot, excludeRoot = happyValue[root], 0  # 包含根节点和不包含根节点的快乐值
    for value in tree[root]:
        data = process(value)  # 子树根节点来和不来的最大快乐值
        # 包含根节点,则子树根节点不能来
        includeRoot += data[1]
        # 不包含根节点,子树根节点可以来,可以不来
        excludeRoot += max(data[0], data[1])
    return [includeRoot, excludeRoot]
data = process(root)
print(max(data[0], data[1]))

发表于 2023-01-14 21:06:51 回复(0)
这题意是真的难搞
10分钟写出来了 结果最后 一直在改建树
友情提示 第二行 是所有人的 快乐值  员工编号 - 1 为下表 去找 快乐值
#include <iostream>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
struct TreeNode {
    int happy;
    std::map<int,TreeNode *> son;
    TreeNode (int x) {
         happy = x;
        son = std::map<int,TreeNode*> ();
    }
};
 struct Info  {
    int come_happy;
    int not_come_happy;
    Info(int a,int b) {
        come_happy = a;
        not_come_happy = b;
    }
};



//这里就需要是后续遍历了

Info dfs(TreeNode * root) {
    //if (root == nullptr) return Info(0,0);
    if (root -> son.empty())
        return Info(root -> happy,0);
    int com = root -> happy;
    int n_com = 0;
    for (std::map<int, TreeNode *>::iterator x = root -> son.begin(); x != root -> son.end(); x ++) {
         Info tmp = dfs(x -> second);
        //可以来 只写下属都不能来
        com += tmp.not_come_happy; 
        // 不来: 直系下属可来可不赖
        n_com += std::max(tmp.come_happy,tmp.not_come_happy);
        
    }
    return Info(com,n_com);
}




int main() {
    int num,boss;
    std:: cin >> num >> boss;
    std::map<int,TreeNode *> map;
    std::vector<int> happy_vec;
    for (int i = 0;i < num; i ++){
        int tmp = 0;
        std::cin >> tmp;
        happy_vec.push_back(tmp);
    }
    TreeNode * root = new TreeNode(happy_vec[boss - 1]);
    map.insert(std::pair<int,TreeNode *>(boss,root));
    for (int i = 1; i < happy_vec.size() ; i ++) {
        int p , self;
        std:: cin >> p >> self;
        TreeNode * node = new TreeNode(happy_vec[self - 1]);//快乐值
        map.insert(std::pair<int,TreeNode *> (self,node));
        if (map.find(p) == map.end()) {
            TreeNode * new_node = new TreeNode(happy_vec[p - 1]);
            map.insert(std::pair<int,TreeNode *>(p,new_node));
        }
        map[p]->son.insert(std::pair<int,TreeNode *> (self,node));
    }
    // 到这里 树已经建立起来了
   // sort(happy_vec.begin(),happy_vec.end());
    //for (auto x : map) std::cout<< x.first;
    // 建树
    Info  rem = dfs(root);
    std:: cout << std:: max(rem.come_happy ,rem.not_come_happy);
    return 0;
}




发表于 2022-07-14 22:04:25 回复(0)
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static class TreeNode{
        //int index;
        int val;
        ArrayList<TreeNode> subordinates;

        public TreeNode(int val){
            //this.index = index;
            this.val = val;
            subordinates = new ArrayList<>();
        }
    }

    public class Info{
        int attend;
        int notAttend;

        public Info(int attend, int notAttend) {
            this.attend = attend;
            this.notAttend = notAttend;
        }
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int rootIndex = sc.nextInt();
        TreeNode[] nodes = new TreeNode[n+1];
        for(int i = 1; i < n + 1; i++){
            nodes[i] = new TreeNode(sc.nextInt());
        }
        for(int j = 0; j < n-1; j++){
            nodes[sc.nextInt()].subordinates.add(nodes[sc.nextInt()]);
        }
        Main main = new Main();

        System.out.println(main.maxHappiness(nodes[rootIndex]));

    }

    public int maxHappiness(TreeNode root){
        Info r = recur(root);
        return Math.max(r.attend, r.notAttend);
    }

    public Info recur(TreeNode root){
        // 如果已经到达基层员工
        if(root.subordinates.isEmpty()) {
            return new Info(root.val, 0);
        }

        int attend = root.val;
        int notAttend = 0;

        for(TreeNode s: root.subordinates){
            Info i = recur(s);
            attend += i.notAttend;
            notAttend += Math.max(i.attend, i.notAttend);
        }
        return new Info(attend, notAttend);

    }
}

发表于 2022-03-26 16:55:56 回复(0)
#include <iostream>
#include <vector>

using namespace std;

void dfs(vector<vector<int>>& g, vector<int>& happies,
         int curr, vector<pair<int, int>>& dp) {
 
  dp[curr].first = happies[curr];
  for (const auto& child : g[curr]) {
    dfs(g, happies, child, dp);
    dp[curr].first += dp[child].second;
    dp[curr].second += max(dp[child].first, dp[child].second);
  }
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int n, root_id;
  cin >> n >> root_id;
  
  vector<int> happies(n + 1);
  for (int i = 1; i <= n; ++i)
    cin >> happies[i];
  
  int u, v;
  vector<vector<int>> g(n + 1);
  for (int i = 0; i < n - 1; ++i) {
    cin >> u >> v;
    g[u].emplace_back(v);
  }
  
  vector<pair<int, int>> dp(n + 1);
  dfs(g, happies, root_id, dp);
  cout << max(dp[root_id].first, dp[root_id].second);
  return 0;
}

发表于 2021-08-04 09:51:07 回复(0)
#include <iostream>
#include <vector>
using namespace std;

struct employee{
    int happy;
    vector<int> subordinates;
};

struct ReturnType{
    int yesMaxHappy;
    int noMaxHappy;
};

ReturnType maxHappy(const employee *v, int head){
    if(v[head].subordinates.size() == 0)
        return {v[head].happy, 0};
    vector<ReturnType> vr;
    for(auto s : v[head].subordinates){
        vr.push_back(maxHappy(v, s));
    }
    //两种情况
    //1. 有head
    int yesMaxHappy = v[head].happy;
    for(auto vri : vr){
        yesMaxHappy += vri.noMaxHappy;
    }
    int noMaxHappy = 0;
    for(auto vri : vr){
        noMaxHappy += max(vri.yesMaxHappy, vri.noMaxHappy);
    }
    return {yesMaxHappy, noMaxHappy};
}

int main(void){
    int n, root;
    cin >> n >> root;
    employee* v = new employee[n + 1];
    for(int i = 1; i < n + 1; i++){
        cin >> v[i].happy;
    }
    int superior, subordiante;
    for(int i = 0; i < n - 1; i++){
        cin >> superior >> subordiante;
        v[superior].subordinates.push_back(subordiante);
    }
    ReturnType r = maxHappy(v, root);
    cout << max(r.noMaxHappy, r.yesMaxHappy) << endl;
    delete []v;
    return 0;
}
本道题仍然是属性DP问题,解法在于将是否考虑头节点
我写这道题出现段错误的原因是 从1开始,而非从0开始
发表于 2021-05-29 15:41:14 回复(0)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int boss = sc.nextInt();
        Map<Integer, Employee> map = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            int happy = sc.nextInt();
            Employee employee = new Employee(happy, new ArrayList<>());
            map.put(i, employee);
        }
        for (int i = 0; i < n - 1; i++) {
            int em = sc.nextInt();
            int sub = sc.nextInt();
            map.get(em).subs.add(map.get(sub));
        }
        Info info = process(map.get(boss));
        System.out.println(Math.max(info.inHappy, info.outHappy));
    }
    
    private static Info process(Employee x) {
        int inHappy = x.happy;
        int outHappy = 0;
        for (Employee sub : x.subs) {
            Info subInfo = process(sub);
            inHappy += subInfo.outHappy;
            outHappy += Math.max(subInfo.inHappy, subInfo.outHappy);
        }
        return new Info(inHappy, outHappy);
    }
}

class Employee {
    public int happy;
    public List<Employee> subs;
    public Employee(int happy, List<Employee> subs) {
        this.happy = happy;
        this.subs = subs;
    }
}

class Info {
    public int inHappy;
    public int outHappy;
    public Info(int inHappy, int outHappy) {
        this.inHappy = inHappy;
        this.outHappy = outHappy;
    }
}

发表于 2021-04-06 15:39:32 回复(0)
import java.util.*;
public class Main {
  static class Node {
    int id;
    int activity;
    List<Node> nexts = new ArrayList<>();

    public Node(int id) {
      this.id = id;
    }
  }

  static class RetType {
    int absent;
    int present;

    public RetType(int absent, int present) {
      this.absent = absent;
      this.present = present;
    }
  }

  static Node[] person;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(), root = sc.nextInt();
    person = new Node[n];
    for (int i = 0; i < n; i++) {
      person[i] = new Node(i);
      person[i].activity = sc.nextInt();
    }
    while (sc.hasNext()) {
      person[sc.nextInt() - 1].nexts.add(person[sc.nextInt() - 1]);
    }
    RetType data = process(person[root - 1]);
    System.out.println(Math.max(data.absent, data.present));
  }

  static RetType process(Node root) {
    int absent = 0, present = root.activity;
    for (Node next : root.nexts) {
      RetType data = process(next);
      absent += Math.max(data.absent, data.present);
      present += data.absent;
    }
    return new RetType(absent, present);
  }
}

发表于 2020-10-20 14:56:55 回复(0)
import sys

n, root = map(int, sys.stdin.readline().split())
happy = [0] + list(map(int, sys.stdin.readline().split()))
chd = [[] for i in range(n+1)]
for i in range(n-1):
    u, v = map(int, sys.stdin.readline().split())
    chd[u].append(v)

def dfs(cur):
    if len(chd[cur]) == 0:
        return happy[cur], 0
    come, ncom = happy[cur], 0
    for c in chd[cur]:
        cm, nc = dfs(c)
        come += nc
        ncom += max(cm, nc)  # cur不来的话,c可以来也可以不来
    return come, ncom

print(max(dfs(root)))

发表于 2020-07-26 21:46:36 回复(0)
有两种解题思路:
#include <iostream>
(720)#include<vector>
#include<map>
(747)#include<string>
using namespace std;
int dfs(int node,vector<int>& happyval,vector<vector<int>>& tree,vector<int>&memo){
    if(memo[node] != -1){
        return memo[node];
    }
    //当前节点node要被获取快乐值
    int sum = 0;
    int len = tree[node].size();
    if(len!=0){
        for(int i = 0;i<len;i++){
            //考虑儿子的儿子
            int _len = tree[tree[node][i]].size();
            if(_len!=0){
                for(int j = 0;j<_len;j++){
                    sum+= dfs(tree[tree[node][i]][j],happyval,tree,memo);
                }
            }
        }
    }
    //注意:包含在外面
    sum += happyval[node];
    int nums = 0;
    //当前节点不被选择
    if(len!=0){
        for(int i = 0;i<len;i++){
            nums+= dfs(tree[node][i],happyval,tree,memo);
        }
    }
    memo[node] = max(sum,nums);
    return memo[node];
}
int* dfstwo(int node,vector<int>& happyval,vector<vector<int>>& tree){
    int* res = new int[2];
    res[0] = 0;
    res[1] = 0;
    //不取这人的快乐值
    int len = tree[node].size();
    for(int i = 0;i<len;i++){
        int* temp = dfstwo(tree[node][i],happyval,tree);
        //不选择当前节点,则其子节点可选可不选,谁大选谁
        res[0] += max(temp[0],temp[1]);
        res[1] += temp[0];
        delete[] temp;
    }
    res[1]+=happyval[node];
    return res;
}
int main() {
    //算法1
   //递归 当前节点+孙子节点 || 儿子节点
    /*
    int n,root;
    cin>>n>>root;
    vector<int> happyval(n+1,0);
    vector<vector<int>> tree(n+1,vector<int>());
    for(int i =1;i<=n;i++){
        int temp;
        cin>> temp;
        happyval[i] = temp;
    }
    for(int i = 0;i<n-1;i++){
        int father ,son;
        cin>>father>>son;
        tree[father].push_back(son);
    }
    vector<int> memo(n+1,-1);
    cout<<dfs(root,happyval,tree,memo)<<endl;
    */
    //优化:减少递归次数
    int n,root;
    cin>>n>>root;
    vector<int> happyval(n+1,0);
    vector<vector<int>> tree(n+1,vector<int>());
    for(int i =1;i<=n;i++){
        int temp;
        cin>> temp;
        happyval[i] = temp;
    }
    for(int i = 0;i<n-1;i++){
        int father ,son;
        cin>>father>>son;
        tree[father].push_back(son);
    }
    int* res = dfstwo(root,happyval,tree);
    cout<<max(res[0],res[1])<<endl;
    delete[] res;
    return 0;
}

发表于 2020-04-03 10:45:45 回复(0)
#include<bits/stdc++.h>
using namespace std;
struct Node{
    // 每个员工的快乐值
    int happiness = 0;
    // 该员工的直接下属
    vector<int>v;
    Node(){v.clear();}
};
struct ReturnType{
    // 包含头节点与不包含头节点的最大快乐值
    int with_head_max;
    int no_head_max;
    ReturnType(int with_head_max,int no_head_max)
    {
        this->with_head_max = with_head_max;
        this->no_head_max = no_head_max;
    }
};

ReturnType getMaxHappiness(vector<Node>& tree,int root)
{
    int with_head = tree[root].happiness;
    int no_head = 0;
    // 该员工没有下属,直接返回
    if(tree[root].v.empty())
        return ReturnType(with_head,no_head);
    // 否则,对其下属节点以同样的要求进行求解
    else{
        for(int sub : tree[root].v)
        {
            // 子节点返回的信息
            ReturnType child_data = getMaxHappiness(tree,sub);
            // 如果选择当前头节点,则其子节点必不可选
            with_head += child_data.no_head_max;
            // 否则,子节点可选可不选,取最优值
            no_head += max(child_data.with_head_max,child_data.no_head_max);
        }
        // 以当前节点为根的树的信息返回给上层
        return ReturnType(with_head,no_head);
    }
}
int main()
{
    int n,root;
    cin>>n>>root;
    vector<Node>tree(n+1);
    //int happy;

    for(int i=1;i<=n;++i)
    {
        cin>>tree[i].happiness;
    }
    int a,b;
    for(int i=1;i<=n-1;++i)
    {
        cin>>a>>b;
        tree[a].v.push_back(b);
    }
    ReturnType ans = getMaxHappiness(tree,root);
    // 最大值产生于: max(取根节点,不取根节点)
    cout<<max(ans.with_head_max,ans.no_head_max);
    return 0;
}
发表于 2020-02-08 10:57:53 回复(0)
import java.util.*;
public class Main {
    //派对的最大快乐值
public static int[] maxHappy(int[] happy, ArrayList<Integer>[] tree, int root) {
    if (tree[root-1] == null) {
        return new int[]{happy[root-1],0};
    }
    else {
        int[] child;
        int happy1 = happy[root-1];
        int happy2 = 0;

        for(int i = 0; i < tree[root-1].size(); i++){
            child = maxHappy(happy, tree, tree[root-1].get(i));
            happy1 += child[1];
            happy2 += child[0];
        }

        if (happy1 > happy2) {
            return new int[] {happy1, happy2};
        }
        else {
            return new int[] {happy2, happy2};
        }
    }
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int root = scanner.nextInt();
    int[] happy = new int[n];

    for(int i = 0; i < n; i++) {
        happy[i] = scanner.nextInt();
    }//happy value of each person

    ArrayList<Integer>[] arr = new ArrayList[n];

    int u, v;
    for(int i = 0; i < n-1; i++) {
        u = scanner.nextInt() - 1;
        v = scanner.nextInt();
        if (arr[u] == null) {
            arr[u] = new ArrayList<>();
        }
        arr[u].add(v);
    }//建立上下级关系

    scanner.close();

    int d = maxHappy(happy, arr, root)[0];
    System.out.println(d);
}
}

发表于 2019-11-19 16:50:09 回复(0)