XMU1456 水体

1456.松鼠采果
Time Limit: 2000 MS         Memory Limit: 65536 K
Total Submissions: 64 (23 users)         Accepted: 21 (20 users)
[ My Solution]
Description
松鼠Squirrel生活在一棵含有n + 1个节点的树上, 它住的窝在0号节点, 当然, 为了生存, 每天它都会出去采果。为了简化问题, 我们假设松果只出现在除了0号节点外的其他n个节点上, Squirrel每天只会从0号节点出发, 去往某个节点采一个松果, 并从原路返回的途中顺带在路过的每个节点上至多采一个松果(可以选择不采)。那么, Squirrel想知道, 至少经过多少天以后, 树上的果子就会全部被它采光了呢?
Input
输入的第一行有一个正整数n (n <= 50,000), 接下来的一行有n个整数ai (1 <= i <= n, 1 <= ai <= 20,000), 第i个数字表示编号为i的节点上的果子数为ai, 再接下来有n行, 每行2个整数x, y (0 <= x, y <= n), 表示两个节点之间有一条边相连, 输入保证给定的图中任意两点间有且仅有一条路径相通。
Output
输出一个整数, 代表需要花费的天数。
Sample Input
3 
3 2 2 
0 1 
1 2 
1 3
Sample Output
4
Source
doraemon @ xmu
[ Submit ] [ Statistic] [ Status ] [ Discuss]
 
http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1456
题意：
一个有n个节点的树 从节点0出发到各个节点去采果子    每次去目的节点采一个果子 返回途中可以采路过的节点的果子  也可以不采 问最少需要多少次能把树上所有的果子采完
思路：对于某一个分支的每个节点 最少需要的次数 取决于当前节点  与  其所有子节点的和的最大值
 
 
 
[cpp]  
#include<stdio.h>  
#include<vector>  
using namespace std;  
vector<int>a[50000+100];  
int val[50000+100],vis[50000+100];  
int DFS(int k)  
{  
    if(vis[k]) return 0;  
    vis[k]=1;  
    if(a[k].size()==0) return val[k];  
     int sum=0;  
     for(int i=0;i<a[k].size();i++)  
         sum+=DFS(a[k][i]);  
     return val[k]>sum?val[k]:sum;  
  
}  
int main()  
{  
     int n,i,x,y,ans;  
     while(scanf("%d",&n)!=EOF)  
     {  
         for(i=0;i<50000+10;i++)  
         {  
             a[i].clear();  
             val[i]=0;vis[i]=0;  
         }  
         for(i=1;i<=n;i++)  
             scanf("%d",&val[i]);  
         for(i=1;i<=n;i++)  
         {  
             scanf("%d %d",&x,&y);  
             a[x].push_back(y);  
             a[y].push_back(x);  
         }  
         ans=DFS(0);  
         printf("%d\n",ans);  
     }  
     return 0;  
       
}

补充：软件开发 , C++ ,