Ural 大學有 NN 名職員，編號為 1～N1～N，
他們的關系就像一棵以校長為根的樹，父節點就是子節點的直接上司，
每個職員有一個快樂指數，用整數 HiHi 給出，其中 1≤i≤N1≤i≤N，
現在要召開一場周年慶宴會，不過，沒有職員愿意和直接上司一起參會，
在滿足這個條件的前提下，主辦方希望邀請一部分職員參會，使得所有參會職員的快樂指數總和最大，求這個最大值，
輸入格式
第一行一個整數 NN，
接下來 NN 行，第 ii 行表示 ii 號職員的快樂指數 HiHi，
接下來 N?1N?1 行，每行輸入一對整數 L,KL,K，表示 KK 是 LL 的直接上司，
輸出格式
輸出最大的快樂指數，
資料范圍
1≤N≤60001≤N≤6000,
?128≤Hi≤127?128≤Hi≤127輸入樣例：
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5輸出樣例：
5
學到了一個表示雙鏈表的新方法：
vector陣串列示雙鏈表，
vector<int> son[N] 相當于一個二維陣列，
垂下來的簾子，
狀態表示： dp [ N ] [ 0 或 1 ] 表示當前編號 N的節點 在被選中或是沒被選中的情況下，其子樹的最大開心值，
狀態計算： dp[x][1] += dp[y][0];（選中狀態）
dp[x][0] += max(dp[y][0], dp[y][1]);（沒被選中狀態）；
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 6010;
int fa[N], happy[N]; // fa陣列用于表示是否有父節點，
// 用于尋找根節點，
int dp[N][2]; // 用 0， 1 兩個整數表示狀態，
int n;
vector<int> son[N];// vector陣串列示雙鏈表，
// 學到了學到了， 雙鏈表居然還可以用vector陣串列示，
void dfs(int x)
{
dp[x][1] = happy[x]; // 搜到后的處理，
dp[x][0] = 0;
for(int i = 0; i < son[x].size(); i ++)
{
int y = son[x][i];
dfs(y);
dp[x][1] += dp[y][0]; // 深搜到底后的處理，
dp[x][0] += max(dp[y][0], dp[y][1]);
}
}
int main()
{
cin.tie(0);
std::ios::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; i++) cin >> happy[i];
for(int i = 1; i <= n - 1; i ++)
{
int x, y;
cin >> x >> y;
son[y].push_back(x);
fa[x] = 1;
}
int root = 0;
for(int i = 1; i <= n; i ++)
if(!fa[i])
{
root = i;
break;
}
dfs(root);
cout << max(dp[root][1], dp[root][0]) << endl;
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/403902.html
標籤：其他