算法课程笔记——自下而上树形DP

#include<bits/stdc++.h>usingnamespacestd;
constintN=100005;
intn,a[N];
longlongdp[N][2];
vector<int> e[N];
voiddfs(intu){
    for(autov:e[u])
    {
        dfs(v);
        dp[u][1]+=dp[v][0];
        dp[u][0]+=max(dp[v][0],dp[v][1]);
    }
    dp[u][1]+=a[u];
}
intmain(){
    cin>>n;
    set<int> st;
    for(inti=1;i<=n;i++) cin>>a[i],st.insert(i);
    for(inti=1,x,y;i<n;++i)
    {
        cin>>x>>y;
        e[y].push_back(x);
        st.erase(x);
    }
    intrt=*st.begin();
    dfs(rt);
    cout<<max(dp[rt][0],dp[rt][1]);
    return0;
}

#include<bits/stdc++.h>usingnamespacestd;
constintN=100005;
vector<int>e[N];
intval[N],dp[N][2];
intd[N];
intn, m, k;
voiddfs(intu,intfa){
    for(autov:e[u])
    {
        if(v==fa) continue;
        dfs(v,u);
        dp[u][0]+=dp[v][1];
        dp[u][1]+=min(dp[v][0],dp[v][1]);
    }
    dp[u][1]+=1;
}
intmain(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n;
    for(inti=1,x,y;i<n;++i)
    {
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1,0);
    cout<<min(dp[1][0],dp[1][1]);
    return0;
}

#include<bits/stdc++.h>usingnamespacestd;
constintN=100005;
vector<int>e[N];
longlonga[N],dp[N][3];
intd[N];
intn;
voiddfs(intu){
    longlongminn=1e18;
    for(autov:e[u])
    {
        dfs(v);
        dp[u][0]+=min({dp[v][0],dp[v][1],dp[v][2]});
        dp[u][1]+=min(dp[v][0],dp[v][1]);
        minn=min(minn,dp[v][0]-min(dp[v][0],dp[v][1]));
        dp[u][2]+=dp[v][1];
    }
    dp[u][0]+=a[u];
    dp[u][1]+=minn;
}
intmain(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n;
    for(inti=1;i<=n;++i)
    {
        intid,m;
        cin>>id;
        cin>>a[id];
        cin>>m;
        while(m--)
        {
            intx;
            cin>>x;
            e[id].push_back(x);
            d[x]++;
        }
    }
    intrt;
    for(inti=1;i<=n;++i)
        if(d[i]==0) rt=i;
    dfs(rt);
    cout<<min(dp[rt][0],dp[rt][1]);
    return0;
}