第二道树形DP，先是MLE。后来仅需改小邻接矩阵的第二个维度到30就过了。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 #define MAXN 6005 6  7 int rat[MAXN]; 8 int dp[MAXN][2]; 9 int adj[MAXN][30];10 bool visit[MAXN];11 int n;12 13 int max(int a, int b) {14     return a>b ? a:b;15 }16 17 void dfs(int r) {18     int i, v;19     20     visit[r] = true;21     dp[r][1] = rat[r];22     for (i=1; i<=adj[r][0]; ++i) {23         v = adj[r][i];24         if (visit[v])25             continue;26         dfs(v);27         // r node not attend, v get the maximum28         dp[r][0] += max(dp[v][0], dp[v][1]);29         // r node attend, v not attend.30         dp[r][1] += dp[v][0];31     }32 }33 34 int main() {35     int i, j, k;36     int a, b;37     38     #ifndef ONLINE_JUDGE39         freopen("data.in", "r", stdin);40     #endif41     42     while (scanf("%d", &n) != EOF) {43         for (i=1; i<=n; ++i)44             scanf("%d", &rat[i]);45             46         memset(adj, 0, sizeof(adj));47         memset(visit, false, sizeof(visit));48         memset(dp, 0, sizeof(dp));49         while (scanf("%d %d", &a, &b)!=EOF && (a||b)) {50             ++adj[a][0];51             adj[a][adj[a][0]] = b;52             ++adj[b][0];53             adj[b][adj[b][0]] = a;54         }55         56         dfs(1);57         printf("%d\n", max(dp[1][0], dp[1][1]));58     }59     60     return 0;61 }