题目描述
Farmer John is gathering the cows. His farm contains a network of N (1 <= N <= 100,000) fields conveniently numbered 1..N and connected by N-1 unidirectional paths that eventually lead to field 1. The fields and paths form a tree.
Each field i > 1 has a single one-way, exiting path to field P_i, and currently contains C_i cows (1 <= C_i <= 1,000,000,000). In each time unit, no more than M_i (0 <= M_i <= 1,000,000,000) cows can travel from field i to field P_i (1 <= P_i <= N) (i.e., only M_i cows can traverse the path).
Farmer John wants all the cows to congregate in field 1 (which has no limit on the number of cows it may have). Rules are as follows:
Time is considered in discrete units.
Any given cow might traverse multiple paths in the same time unit. However, no more than M_i total cows can leave field i (i.e., traverse its exit path) in the same time unit.
- Cows never move *away* from field #1.
In other words, every time step, each cow has the choice either to
a) stay in its current field
b) move through one or more fields toward field #1, as long as the bottleneck constraints for each path are not violated
Farmer John wants to know how many cows can arrive in field 1 by certain times. In particular, he has a list of K (1 <= K <= 10,000) times T_i (1 <= T_i <= 1,000,000,000), and he wants to know, for each T_i in the list, the maximum number of cows that can arrive at field 1 by T_i if scheduled to optimize this quantity.
Consider an example where the tree is a straight line, and the T_i list contains only T_1=5, and cows are distibuted as shown:
Locn: 1---2---3---4 <-- Pasture ID numbers
C_i: 0 1 12 12 <-- Current number of cows
M_i: 5 8 3 <-- Limits on path traversal; field 1 has no limit since it has no exit
The solution is as follows; the goal is to move cows to field 1: Tree: 1---2---3---4
t=0 0 1 12 12 <-- Initial state
t=1 5 4 7 9 <-- field 1 has cows from field 2 and 3 t=2 10 7 2 6
t=3 15 7 0 3
t=4 20 5 0 0
t=5 25 0 0 0
Thus, the answer is 25: all 25 cows can arrive at field 1 by time t=5.
Farmer John有一张N个农场构成的网络(1 <= N <= 100,000) ，我们将农场标记为1N。 农场被N-1条单向道路连接，保证从任何一个农场可以到达1号农场。FJ想让奶牛到1号农场集中 （P.S. 至于要做什么我也不知道）。 对于每个农场i > 1都有一条单独的单向道路通往P_i，并且这个农场里有C_i只奶牛 （1 <= C_i <= 1,000,000,000）。在每个单位时间里，这条道路允许不超过M_i (0 <= M_i <= 1,000,000,000)只奶牛从农场i走到农场P_i (1 <= P_i <= N)。 Farmer John 想让所有的奶牛都集中在1号农场（农场容纳奶牛的数量是没有限制的）。 下面是奶牛集中到1号农场过程的规则：
我们认为时间是离散的 * 任何奶牛都可以在一个单位时间里走过任意多条道路。但是，必须满足每条道路的上限M_i。
- 奶牛从来不会离开1号农场。 换句话说，每一个单位时间，每只奶牛可以选择下面行动之一：
a) 留在当前的农场
b) 经过一条或者多条道路，向1号农场移动。
同样，需要满足每条道路的上限M_i。
FJ想知道有多少奶牛可以在某个特定的时刻到达1号农场。
特别的，他有一张列着K (1 <= K <= 10,000) 个时间T_i (1 <= T_i <= 1,000,000,000)的单子，他想知道对于每个T_i，如果采用最优 的策略在这个时刻结束时最多能有多少奶牛到达1号农场。
输入输出格式
输入格式：
Line 1: Two space-separated integers: N and K
- Lines 2..N: Line i (not i+1) describes field i with three
space-separated integers: P_i, C_i, and M_i
- Lines N+1..N+K: Line N+i contains a single integer: T_i
输出格式：
- Lines 1..K: Line i contains a single integer that is the maximum number of cows that can arrive at field 1 by time T_i.
输入输出样例
4 1
1 1 5
2 12 7
3 12 3
5
25
1 #include <algorithm>
2 #include <iostream>
3 #include <cstring>
4 #include <cstdio>
5 #include <queue>
6 typedef long long LL;
7 using namespace std;
8 const int N=100010;
9 struct Query{LL t,res;int id;}ask[N];
10 bool cmp1(Query x,Query y){return x.t<y.t;}
11 bool cmp2(Query x,Query y){return x.id<y.id;}
12 struct Node{
13 LL t;int x;Node(LL t_=0,int x_=0){t=t_;x=x_;}
14 friend bool operator<(Node a,Node b){return a.t>b.t;}
15 };
16 priority_queue<Node>q;
17 int fa[N],anc[N],lim[N];
18 LL cow[N],pass[N];
19 int Find(int x){
20 if(anc[x]==x)return x;
21 return anc[x]=Find(anc[x]);
22 }
23 int n,Q;
24 int main(){
25 freopen("bottleneck.in","r",stdin);
26 freopen("bottleneck.out","w",stdout);
27 scanf("%d%d",&n,&Q);
28 for(int i=1;i<=n;i++)
29 anc[i]=i;
30 for(int i=2;i<=n;i++){
31 scanf("%d",&fa[i]);
32 scanf("%lld",&cow[i]);
33 scanf("%lld",&lim[i]);
34 pass[fa[i]]-=lim[i];
35 pass[i]+=lim[i];
36 }
37 for(int i=1;i<=Q;i++){
38 scanf("%lld",&ask[i].t);
39 ask[i].id=i;
40 }sort(ask+1,ask+Q+1,cmp1);
41
42 for(int i=2;i<=n;i++)
43 if(pass[i]>0){
44 LL t=cow[i]/pass[i];
45 q.push(Node(t,i));
46 }
47
48 int p=1,x,tp;
49 while(!q.empty()&&p<=Q){
50 while(p<=Q&&ask[p].t<=q.top().t)
51 ask[p].res=cow[1]-pass[1]*ask[p].t,p++;
52 if(anc[q.top().x]!=q.top().x){q.pop();continue;}
53 x=q.top().x;tp=Find(fa[x]);cow[tp]+=cow[x];
54 pass[tp]+=pass[x];anc[x]=tp;
55 if(pass[tp]>0){
56 LL t=cow[tp]/pass[tp];
57 q.push(Node(t,tp));
58 }
59 q.pop();
60 }sort(ask+1,ask+Q+1,cmp2);
61 for(int i=1;i<=Q;i++)
62 printf("%lld\n",ask[i].res);
63 return 0;
64 }