第一道树形DP
根据左儿子 右兄弟 将多叉树转化成二叉树 结构体里保存取这个节点和不取这个节点的最大值
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<stdlib.h> 5 #include<algorithm> 6 using namespace std; 7 #define N 6010 8 struct node 9 { 10 int child,father,brother; 11 int nmax,ymax,v; 12 void init() 13 { 14 nmax = ymax=0; 15 child=father=brother=0; 16 } 17 }tr[N]; 18 int de[N]; 19 void dfs(int u) 20 { 21 int child = tr[u].child; 22 while(child) 23 { 24 dfs(child); 25 tr[u].ymax += tr[child].nmax; 26 tr[u].nmax += max(tr[child].ymax,tr[child].nmax); 27 child = tr[child].brother; 28 } 29 } 30 int main() 31 { 32 int i,k,n,u,v; 33 while(cin>>n) 34 { 35 memset(de,0,sizeof(de)); 36 for(i = 1 ; i <= n ;i++) 37 { 38 cin>>k; 39 tr[i].init(); 40 tr[i].ymax = k; 41 } 42 while(cin>>u>>v) 43 { 44 if(!u&&!v) break; 45 tr[u].father = v; 46 tr[u].brother = tr[v].child; 47 tr[v].child = u; 48 de[u]++; 49 } 50 int ans = 0; 51 for(i = 1; i <= n ; i++) 52 { 53 if(!de[i]) 54 { 55 dfs(i); 56 ans = max(max(tr[i].nmax,tr[i].ymax),ans); 57 } 58 } 59 cout<<ans<<endl; 60 } 61 62 return 0; 63 }