编程之美复赛，运输货物，hihocoder 1168

题目1 : 运输货物

时间限制:2000ms

单点时限:1000ms

内存限制:256MB

描述

Z国有n个城市，编号为1, 2, …, n。城市间通过n – 1条道路相连，任意两个城市间有且仅有一条路径可以相互到达。每个城市都有一些货物，政府希望将所有的货物运送到港口城市s以便出口。由于交通条件限制，每一条道路上单位时间只能通过1单位量的货物，这导致运输所有货物可能非常耗时。因而，政府希望知道，最快什么时候能将所有货物运送到港口。

输入

第一行一个整数T，表示数据组数，以下是T组数据。

每组数据第一行有两个整数n和s，表示城市个数和港口城市的编号。接下来n - 1行每行两个整数i和j，表示城市i和j之间有一条道路。接下来n行每行一个数x，表示各城市的货物数量。

输出

对每组数据输出一行"Case #X: Y"，X表示数据编号（从1开始），Y为完成运输任务的最短时间。

数据范围

1 ≤ T ≤ 20

小数据

1 ≤ n ≤ 500

0 ≤ x ≤ 20

大数据

1 ≤ n ≤ 100000

0 ≤ x ≤ 100000

样例输入

Case #1: 1
Case #2: 6

解法：树型DP，在父节点合并子节点货物流的的时间段和父节点货物流的时间段，对于页节点v货物流的时间段是（0，x[v]);
答案就是s的子节点的最后一段货物流的最大值。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <vector>
 5 using namespace std;
 6 typedef long long LL;
 7 const int N = 100010;
 8 vector<int> e[N];
 9 int n,s;
10 int x[N];
11 LL ans;
12 void dfs(int v,int fa,vector<pair<LL, LL> > &g)
13 {
14     vector<pair<LL,LL> > vp;
15     if(x[v])
16     {
17         vp.push_back(make_pair(0,x[v]));
18     }
19     for(int i=0;i<e[v].size();i++)
20     {
21         if(e[v][i]!=fa)
22         {
23             vector<pair<LL,LL> > tp;
24             dfs(e[v][i],v,tp);
25             if(v==s&&tp.size()!=0)
26             {
27                 ans = max(ans,tp[tp.size()-1].second);
28             }
29             for(int j=0;j<tp.size();j++)
30             {
31                 tp[j].first++;
32                 tp[j].second++;
33                 vp.push_back(tp[j]);
34             }
35         }
36     }
37     sort(vp.begin(),vp.end());
38     if(vp.size()==0) return ;
39     int st = vp[0].first, ed = vp[0].second;
40     for(int i=1;i<vp.size();i++)
41     {
42         if(vp[i].first<=ed)
43         {
44             ed += vp[i].second - vp[i].first;
45         }
46         else
47         {
48             g.push_back(make_pair(st,ed));
49             st = vp[i].first;
50             ed = vp[i].second;
51         }
52     }
53     g.push_back(make_pair(st,ed));
54 }
55 int main(){
56     int T;
57     scanf("%d",&T);
58     for(int ks = 1; ks <= T; ks++)
59     {
60         scanf("%d%d",&n,&s);
61         for(int i=0;i<=n;i++)
62             e[i].clear();
63         for(int i=0;i<n-1;i++)
64         {
65             int u,v;
66             scanf("%d%d",&u,&v);
67             e[u].push_back(v);
68             e[v].push_back(u);
69         }
70         for(int i=1;i<=n;i++)
71         {
72             scanf("%d", x+i);
73         }
74         x[s] = 0;
75         vector<pair<LL,LL> > vec;
76         ans = 0;
77         dfs(s,-1,vec);
78         printf("Case #%d: %lld
",ks,ans);
79     }
80 }