CPP习题-树型DP

C++ 进阶

树型DP（动态规划）

例题ACWING285

const int N = 1e4 + 5;
int h[N], cnt, nxt[N], to[N], f[N][2], w[N], fa[N];
int  l, k, rt, n;

邻接表

void add(int a, int b) {
    to[++cnt] = b, nxt[cnt] = h[a], h[a] = cnt;
}

以邻接表dfs为基础

void dfs(int u) {
    f[u][1] = w[u]; //如果自己要来先把自己的快乐加上
    for (int i = h[u]; i; i = nxt[i]) {
        int v = to[i];

        //DP的部分
        dfs(v);//先递归，因为上面要使用下面的结果
        f[u][1] += f[v][0]; //自己要来
        f[u][0] += max(f[v][0], f[v][1]); //自己不来


    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    for (int i = 1; i < n; i++) {//请勿用while(n--)
        cin >> l >> k;
        add(k, l);
        fa[l] = k;
    }
    for (int i = 1; i <= n; i++)
        if (fa[i] == 0)
            rt = i;
    dfs(rt);
    cout << max(f[rt][1], f[rt][0]);
    return 0;
}