lg1352 发表于 2018-02-26 | 分类于 算法 , DP | 阅读数 次 链接:lg1352 题解 模板题 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(regsiter int i=x;i>=y;--i)using namespace std;const int N=1e4;int fa[N],r[N],dp[N][2],vis[N];int n,root=1;template <typename T>inline void read(T&x){ x=0;char c;int sign=1; do{ c=getchar(); if(c=='-')sign=-1;}while(c<'0'||c>'9'); do{ x=x*10+c-'0'; c=getchar();}while(c>='0'&&c<='9'); x*=sign;}void tdp(int node){ vis[node]=1; rep(i,1,n)if(!vis[i]&&fa[i]==node){ tdp(i); dp[node][1]+=dp[i][0]; dp[node][0]+=max(dp[i][1],dp[i][0]); }}int main(){ read(n); rep(i,1,n)read(dp[i][1]); rep(i,1,n-1){ int x,y; read(x);read(y); fa[x]=y; } rep(i,1,n)if(!fa[i]){ root=i;break; } tdp(root); printf("%d",max(dp[root][1],dp[root][0])); return 0;}