2010年1月30日星期六.sgu143 树状动态规划
sgu143:Tree DP
题目给出n(1 <= n <= 16 000)个点，n-1条边，每个点都有一个权值，求最大连通子图。
由于题目给出的图边比点少一个，随意也就是一棵树，所以题目所求的也就变成了最大连通子树。
可以深搜，每个点的的最大连通子树的权等于这个点的权值+它所有未访问邻接点的正权和。
1 const int N = 16100;
2 int n,val[N],vis[N],res;
3 vector<int> g[N];
4 //http://www.cppblog.com/schindlerlee
5 int dfs(int u)
6 {
7 vis[u] = true;
8 int sz = g[u].size(),i, cur = val[u],tmp;
9 for (i = 0;i < sz;i++) {
10 if (!vis[g[u][i]] && (tmp = dfs(g[u][i])) && tmp > 0) {
11 cur += tmp;
12 }
13 }
14 if(cur > res) { res = cur; }
15 return cur;
16 }
res 初值为-inf,最后res就是结果。