没有上司的舞会
挑没有直接边相连的点的数量最多。
f[u, 0]所有从以u为根的子树中选择,并且不选u这个点的方案。
f[u, 1]所有从以u为根的子树中选,并且选择u这个点的方案。
属性Max;
f(u, 0):
]
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 6010; int n, happy[N], h[N], ne[N], e[N], idx; int f[N][2]; bool has_father[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void dfs(int u) { f[u][1] = happy[u]; for(int i = h[u]; i!=-1;i = ne[i]) { int j = e[i]; dfs(j); f[u][0] += max(f[j][0], f[j][1]); f[u][1] += f[j][0]; } } int main() { cin>>n; for(int i = 1; i <= n; i++) cin>>happy[i]; memset(h, -1, sizeof h); for(int i = 0; i < n - 1; i++) { int a, b; cin>>a>>b; has_father[a] = true; add(b, a); } int root = 1; while(has_father[root]) root++; dfs(root); cout<<max(f[root][0], f[root][1])<<endl; }