树形dp

kamikuQAQ · 2025-09-11 23:47:33 · 个人记录

树形dp

树上子树问题 例题B3861子树和

首先依旧是图论老惯例先建双向边树，子树和的概念就是就是子树中有多少个结点，然后以1为祖宗一直从下用dfs遍历，需要注意的是在找儿子的时候一定要先递归再算答案，直到找到了叶子结点再把答案给自己的祖先

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+7;
vector<int>g[maxn];
void addline(int u,int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}
int siz[maxn];
void dfs(int u,int fa) {
    siz[u]=1;
    for(int i=0;i<g[u].size();i++) {
        int v=g[u][i];
        if(v!=fa) {
            dfs(v,u);
            siz[u]+=siz[v];
        }
    }
}
int main() {
    int n;
    cin>>n;
    for(int i=2;i<=n;i++) {
        int f;
        cin>>f;
        addline(i,f);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++) {
        cout<<siz[i]<<'\n';
    }
    return 0;
}

P1352

本题多加了要么选下面一个点可以选或不选的条件，于是我们选定一个点为起点赋初始值为这个点的点权，然后照例跑dfs如果子树的点权和为负数则+0作为不选的条件，否则选上

#include<bits/stdc++.h>
using namespace std;
const int maxn = 16007;
vector<int>g[maxn];
void addline(int u,int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}
int r[maxn],dp[maxn];
void dfs(int u,int fa) {
    dp[u]=r[u];
    for(int i=0;i<g[u].size();i++) {
        int v=g[u][i];
        if(v!=fa) {
            dfs(v,u);
            dp[u]+=max(0,dp[v]);
        }
    }
}
signed main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>r[i];
    }
    for(int i=1;i<n;i++) {
        int a,b;
        cin>>a>>b;
        addline(a,b);
    }
    dfs(1,0);
    int maxx=-1e9;
    for(int i=1;i<=n;i++) {
        maxx=max(maxx,dp[i]);
    }
    cout<<maxx;
    return 0;
}