题意:给你一颗树，树上每个节点都有一个权值，父亲和儿子不能同时选，求最大权值
dp[u][0]表示不选u节点时的最大权值，dp[u][1]表示选u时的最大权值。
dp[u][1]+=dp[v][0]，选父亲的时候，就加上不选儿子的
dp[u][0]=max(dp[v][0],dp[v][1])，不选父亲的时候，可以选儿子，也可以不选，取最大的。
记录下有哪个点没有父亲，那就可以用那个点跑一次dfs就可以了
#include <iostream> #include <cstdio> #include <cstring> #include <ctime> #include <algorithm> #include <cstdlib> #include <cmath> #include <map> #include <set> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double db; #define X first #define Y second #define mp(a,b) make_pair(a,b) #define pb push_back #define sd(x) scanf("%d",&(x)) #define Pi acos(-1.0) #define sf(x) scanf("%lf",&(x)) #define ss(x) scanf("%s",(x)) #define maxn 50005 const int inf=0x3f3f3f3f; const ll mod=1000000007; #define N 6005 int dp[N][2],vis[N],po[N]; int e,n; int head[N]; struct node { int v,next; }edge[N]; void addedge(int u,int v) { edge[e].v=v; edge[e].next=head[u]; head[u]=e++; } void init() { memset(head,-1,sizeof head); memset(vis,0,sizeof vis); memset(dp,0,sizeof dp); e=0; for(int i=1;i<=n;i++)sd(po[i]); int u,v; while(scanf("%d%d",&u,&v),u+v) { addedge(v,u); vis[u]=1; } } void dfs(int u) { dp[u][0]=0; dp[u][1]=po[u]; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; dfs(v); dp[u][1]+=dp[v][0]; dp[u][0]+=max(dp[v][0],dp[v][1]); } } void work() { int a; for(a=1;a<=n;a++) if(!vis[a])break; dfs(a); cout<<max(dp[a][0],dp[a][1])<<endl; } int main() { #ifdef local freopen("in","r",stdin); //freopen("out","w",stdout); int _time=clock(); #endif while(cin>>n) { init(); work(); } #ifdef local printf("time: %d ",int(clock()-_time)); #endif }