洛谷 P1352 没有上司的舞会

忘是亡心i 2023-07-18 05:56 7阅读 0赞

## 题目描述 ##

某大学有 n 个职员，编号为 1…n。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 ri，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

## 输入格式 ##

输入的第一行是一个整数 n。

第 2 到第 (n+1)行，每行一个整数，第 (i+1)行的整数表示 iii 号职员的快乐指数 ri。

第 (n+2) 到第 (2n+1) 行，每行输入一对整数 l,k 代表 k 是 l 的直接上司。

## 输出格式 ##

输出一行一个整数代表最大的快乐指数。

## 输入输出样例 ##

**输入 \#1**

7
    1
    1
    1
    1
    1
    1
    1
    1 3
    2 3
    6 4
    7 4
    4 5
    3 5
    0 0

**输出 \#1**

## 说明/提示 ##

数据规模与约定

对于 100% 的数据，保证 1≤n≤6×10^3，−128≤ri≤127，1≤l,k≤n，且给出的关系一定是一棵树。

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 60002;
    
    vector<int> adj[MAXN];
    int happy[MAXN];   //每个职员的快乐指数 
    int dp[MAXN][2];    
    int father[MAXN];  //father[i] = j;表示i的直接上司是j。 
    
    void DFS(int u){  //这个DFS递归，不需要写明递归出口 
    	dp[u][0] = 0;         //以u为根的子树的快乐值（u不去的时候） 
    	dp[u][1] = happy[u];  //以u为根的子树的快乐值（u去的时候） 
    	for(int i=0;i<adj[u].size();i++){
    		int v = adj[u][i]; 
    		DFS(v);
    		dp[u][0] += max(dp[v][0],dp[v][1]);  //此时u的子节点v可以去也可以不去。 
    		dp[u][1] += dp[v][0];                //此时u的子节点v一定不去。 
    	}
    }
    
    int main(){
    	int n;
    	int l,k;
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>happy[i];
    	}
    	for(int i=1;i<=n;i++){
    		father[i] = i;  //直接上司是自己。 
    	} 
    	for(int i=1;i<=n;i++){
    		cin>>l>>k;
    		adj[k].push_back(l);  //因为是树，所以是单向的，更有利于DFS。 
    		father[l] = k;  //改变l的直接上司为k 
    	}
    	
    	int root = -1;  //找到这棵树的根。 
    	for(int i=1;i<=n;i++){
    		if(father[i] == i){
    			root = i;
    			break; 
    		}
    	}
    	
    	DFS(root);
    	int ans = max(dp[root][0],dp[root][1]);
    	cout<<ans<<endl; 
    	return 0;
    }