树形 DP 的父子契约

#include <bits/stdc++.h>
using namespace std;

int main() {
vector<vector<int>>g{{1},{0,2},{1}};vector<int>w{5,6,5},take(3),skip(3);
function<void(int,int)>dfs=[&](int u,int p){take[u]=w[u];for(int v:g[u])if(v!=p){dfs(v,u);take[u]+=skip[v];skip[u]+=max(take[v],skip[v]);}};
dfs(0,-1);cout<<max(take[0],skip[0])<<" "<<skip[0];
}

#include <bits/stdc++.h>
using namespace std;

int main() {
vector<vector<int>>g{{1},{0,2},{1}};vector<int>w{5,6,5},take(3),skip(3);
function<void(int,int)>dfs=[&](int u,int p){take[u]=w[u];for(int v:g[u])if(v!=p){dfs(v,u);take[u]+=skip[v];skip[u]+=max(take[v],skip[v]);}};
dfs(0,-1);cout<<max(take[0],skip[0])<<" "<<skip[0];
}