1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
|
#include<algorithm> #include<cstring> using namespace std; namespace io{ #define re register #define ll long long #define inf 0x3f3f3f3f #define il inline #define in1(a) read(a) #define in2(a,b) in1(a),in1(b) #define in3(a,b,c) in2(a,b),in1(c) #define in4(a,b,c,d) in2(a,b),in2(c,d) il void (ll &x){ x=0;ll f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} x*=f; } il void read(int &x){ x=0;int f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} x*=f; } }using namespace io; #define N 100005 int n,en; int front[N],x[N],y[N],z[N]; ll f[N][4]; struct edge{ int v,next; }e[N<<1]; il void add(int u,int v){ en++; e[en].v=v; e[en].next=front[u]; front[u]=en; } void dfs(int u,int fa){ f[u][1]=x[u]; f[u][2]=y[u]; f[u][3]=z[u]; for(re int i=front[u];i;i=e[i].next){ int v=e[i].v; if(v==fa) continue; dfs(v,u); f[u][1]+=max(f[v][2],f[v][3]); f[u][2]+=max(f[v][1],f[v][3]); f[u][3]+=max(f[v][1],f[v][2]); } } int main(){ int u,v; read(n); for(re int i=1;i<=n-1;i++) in2(u,v),add(u,v),add(v,u); for(re int i=1;i<=n;i++) in3(x[i],y[i],z[i]); dfs(1,1); printf("%lld",max(f[1][1],max(f[1][2],f[1][3]))); return 0; }
|
近期评论