记录编号	346141	评测结果	AAAAAAAAA
题目名称	[USACO Jan11]瓶颈	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.265 s
提交时间	2016-11-11 21:43:25	内存使用	2.72 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
typedef long long LL;
using namespace std;
const int N=100010;
struct Query{LL t,res;int id;}ask[N];
bool cmp1(Query x,Query y){return x.t<y.t;}
bool cmp2(Query x,Query y){return x.id<y.id;}
struct Node{
  LL t;int x;Node(LL t_=0,int x_=0){t=t_;x=x_;}
  friend bool operator<(Node a,Node b){return a.t>b.t;}
};
priority_queue<Node>q;
int fa[N],anc[N],lim[N];
LL cow[N],pass[N];
int Find(int x){
  if(anc[x]==x)return x;
  return anc[x]=Find(anc[x]);
}
int n,Q;
int main(){
  freopen("bottleneck.in","r",stdin);
  freopen("bottleneck.out","w",stdout);
  scanf("%d%d",&n,&Q);
  for(int i=1;i<=n;i++)
    anc[i]=i;
  for(int i=2;i<=n;i++){
    scanf("%d",&fa[i]);
    scanf("%lld",&cow[i]);
    scanf("%lld",&lim[i]);
    pass[fa[i]]-=lim[i];
    pass[i]+=lim[i];
  }
  for(int i=1;i<=Q;i++){
    scanf("%lld",&ask[i].t);
    ask[i].id=i;
  }sort(ask+1,ask+Q+1,cmp1);

  for(int i=2;i<=n;i++)
    if(pass[i]>0){
      LL t=cow[i]/pass[i];
      q.push(Node(t,i));
    }

  int p=1,x,tp;
  while(!q.empty()&&p<=Q){
    while(p<=Q&&ask[p].t<=q.top().t)
      ask[p].res=cow[1]-pass[1]*ask[p].t,p++;
    if(anc[q.top().x]!=q.top().x){q.pop();continue;}
    x=q.top().x;tp=Find(fa[x]);cow[tp]+=cow[x];
    pass[tp]+=pass[x];anc[x]=tp;
    if(pass[tp]>0){
      LL t=cow[tp]/pass[tp];
      q.push(Node(t,tp));
    }
    q.pop();
  }sort(ask+1,ask+Q+1,cmp2);
  for(int i=1;i<=Q;i++)
    printf("%lld\n",ask[i].res);
  return 0;
}