派对的最大快乐值

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]);
        }
    }
}

使用邻接矩阵建图之后，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;
}

#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;
}

#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;
}

//树形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;
}

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]))

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);

    }
}

#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;
}

#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;
}

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;
    }
}

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);
  }
}

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)))

#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;
}

#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;
}

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);
}
}