题目传送门//res tp poj
题意
给出一棵有权树，求一个节点集的权值和，满足集合内的任意两点不存在边
分析
每个点有选中与不选中两种状态，对于第\(i\)个点，记选中为\(sel_i\)，不选中为\(insel_i\)
若某一节点选中，则其子节点都不能选中。
若某一节点不选中，则其子节点有两种选择：1.选中 2.不选中
故
\[sel_i = val_i +\sum_j insel_j
\]
\]
\[insel_i = \sum_j max\{insel_j,sel_j\}
\]
\]
其中\(j\) 是\(i\)的子节点，\(val_i\)是节点\(i\)的权值
设\(rt\)为该树的根
则答案为
\[ans = max\{sel_{rt},insel_{rt}\}
\]
\]
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i = (a);i>=(b);--i)
#define fo(i,a,b) for(int i =(a);i<(b);++i)
#define de(x) cout<<#x<<" = "<<x<<endl;
#define endl '\n'
#define ls(p) ((p)<<1)
#define rs(p) (((p)<<1)|1)
using namespace std;
typedef long long ll;
const int mn = 6e3 + 10;
int n;
int u[mn],inu[mn];
int val[mn];
struct E{
int firs,lasts;
int fa;
int nextbro;
}e[mn];
void dfs(int r){
int tpos = e[r].firs;
while(tpos){
dfs(tpos);
tpos = e[tpos].nextbro;
}
tpos = e[r].firs;
u[r] += val[r];
while(tpos){
u[r] += inu[tpos];
inu[r] += max(inu[tpos],u[tpos]);
tpos = e[tpos].nextbro;
}
}
int main(){
scanf("%d",&n);
rep(i,1,n)scanf("%d",&val[i]);
int tf,ts;
rep(i,1,n){
scanf("%d %d",&ts,&tf);
if(e[tf].firs){
e[e[tf].lasts].nextbro = ts;
e[tf].lasts = ts;
}
else{
e[tf].firs = e[tf].lasts = ts;
}
e[ts].fa = tf;
}
int root = 1;
while(e[root].fa) root = e[root].fa;
//de(root)
dfs(root);
printf("%d\n",max(u[root], inu[root]));
}