简单树形dp题目

洛谷P1352 没有上司的舞会

树上dp。a[i]表示结点i不选时的最优解，b[i]表示选上结点i时的最优解。a[i] = max(b[j],j为i的孩子)，b[i] = max(a[j],j为i的孩子).
这题给出的是明确的一颗树，即有向图，父亲，孩子结点都是明确的。

//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 6050;
int w[maxn];
vector<int> v[maxn];
int a[maxn],b[maxn];      //i 不来  来
int vis[maxn],vis1[maxn],vis2[maxn];   //vis1 不来   vis2 来
int dfs(int root,int flag);        //flag=0表示求root不来的最大值   flag=1表示求root来的最大值
int main(){
    //std::ios::sync_with_stdio(false);
    int n,k,l,root;
    cin >> n;
    for (int i=1;i<=n;i++)  cin >> w[i];
    for (int i=1;i<n;i++){
        cin >> l >> k;
        v[k].push_back(l);
        vis[l] = 1;
    }
    for (int i=1;i<=n;i++)  if (vis[i]==0){
        root = i;
        break;
    }
    //int ans = max(dfs(root,1),dfs(root,0));
    //cout << ans;
    cout << max(dfs(root,1),dfs(root,0));
    return 0;
}
int dfs(int root,int flag){
    if (flag){
        if (vis2[root]) return b[root];
        b[root] = w[root];
        int len = v[root].size();
        for (int i=0;i<len;i++)
            b[root] += dfs(v[root][i],0);
        vis2[root] = 1;
        return b[root];
    }else{
        if (vis1[root]) return a[root];
        int len = v[root].size();
        for (int i=0;i<len;i++)
            a[root] += max(dfs(v[root][i],0),dfs(v[root][i],1));
        vis1[root] = 1;
        return a[root];
    }
    return 0;
}

洛谷P1122 最大子树和

和上一题不同，这题没有明确哪个是父母结点，哪个是孩子结点。
G存图，a存权值，ans[i]表示结点i选上时的最优解，ans里的最大值就是答案。
如何解决父亲孩子结点不明确的情况？用vis来标记一下，如果vis[i]=1，那么说明i结点在访问当前root结点之前就已经访问过了，i不可以是root的孩子，一定是父母结点，就这样，，，。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 16500;
int n,c,b;
vector<int> G[maxn];
int vis[maxn],a[maxn],ans[maxn],res;
int dfs(int root){
    vis[root] = 1;
    int len = G[root].size();
    ans[root] = a[root];
    for (int i=0;i<len;i++) if (!vis[G[root][i]])
        ans[root] = max(ans[root],ans[root]+dfs(G[root][i]));
    res = max(res,ans[root]);
    return ans[root];
}
int main(){
    cin >> n;
    for (int i=1;i<=n;i++)  cin >> a[i];
    for (int i=1;i<n;i++){
        cin >> c >> b;
        G[c].push_back(b);
        G[b].push_back(c);
    }
    dfs(1);
    cout << res;
    return 0;
}