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; }
