Input Employees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go T lines that describe a supervisor relation tree. Each line of the tree specification has the form:
L K
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0
Output Output should contain the maximal sum of guests' ratings.
Sample Input
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
Sample Output
5
连接表存储孩子
#include#include #include #include using namespace std; #define N 6005 int dp[N][2],father[N]; int n; int head[N] ; int num; struct stud{ int to; int next; }e[N*2]; void add(int s,int to) { e[num].to=to; e[num].next=head[s]; head[s]=num++; } void dfs(int x) { int i,j; for(i=head[x];i!=-1;i=e[i].next) { int to=e[i].to; dfs(to); dp[x][1]+=dp[to][0]; dp[x][0]+=max(dp[to][1],dp[to][0]); } } int main() { int i,j; while(~scanf("%d",&n)) { memset(dp,0,sizeof(dp)); memset(father,0,sizeof(father)); memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) scanf("%d",&dp[i][1]); int s,e; num=0; while(scanf("%d%d",&s,&e),s+e) { father[s]=e; add(e,s); } i=1; while(father[i]) i=father[i] ; dfs(i); printf("%d\n",max(dp[i][1],dp[i][0])); } return 0; }