给出的是一棵树，要求这棵树的权值最大的连通子图的权值。
　　树型DP可以：f(T)=sum{f(t)|f(t)>0,t是T的子树}。
　　存图用邻接表。
　　这样DP的话，树根肯定要被选入连通子图，所以还要枚举树根。复杂度是O(n^2)，承受不了。
　　可以边DP边更新权值最大的连通子图的权值。
　　Submit 1: MLE on 8。去掉调试用的成员id。
　　Submit 2: MLE on 8。调整一下结构吧，不用程序员式的写法了，换个ws的。
　　Submit 3: MLE on 8。乱改一下。
　　Submit 4: TLE on 8。不仅TLE，而且MLE。看cpp标程，改用vector。
　　Submit 5: TLE on 8。这次没有MLE了。不用vector<vector>了，就用vector类型的数组。
　　Submit 6: AC。
　　感觉SGU上用list有问题，好像已经是第2次list过不去了。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <cstdio>
#include <vector>
using namespace std;
 
struct treenode
{
    int profit;
    bool visited;
    treenode():visited(false){};
};
 
int maxprofit=-16000000;
vector<int> map[16000];
treenode town[16000];
 
void count(int T)
{
    town[T].visited=true;
    for (vector<int>::iterator i=map[T].begin();i!=map[T].end();i++) if (!town[*i].visited)
    {
        count(*i);
        if (town[*i].profit>0) town[T].profit+=town[*i].profit;
    }
    maxprofit=max(town[T].profit,maxprofit);
}
 
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&town[i-1].profit);
    for (int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        a--; b--;
        map[a].push_back(b);
        map[b].push_back(a);
    }
    count(0);
    printf("%d\n",maxprofit);
    return 0;
}