P3006

来一个无脑线段树合并做法。

考虑记前 $t$ 秒有 $f_u(t)$ 头牛能通过 $u$ 点到父亲的边。则有：

$f_u(t)=\min(m_ut,\sum_{v\in son_u}f_v(t))$

并且有个显然的结论：$m_ut\ge\sum_{v\in son_u}f_v(t)$ 的 $t$ 是一段前缀。然后可以二分出分界点，考虑怎么处理 $f_u$。

发现分界点后面的是一个分段函数，前面则是 $f_u(t)=m_ut$ 这个一次函数，所以可考虑将这个函数用线段树维护，维护每个点的 $k,b$。需要支持区间加一次函数，区间赋 $0$，以及合并。总复杂度 $O(n\log^2 V)$。

但是金钩爷 @dieselhuang 发现这是凸的，故可以 $O(n\log V)$ 也是线段树合并解决。/bx

code：

bool Mbe;
int n,m,k=1e9,sum,rt[N],a[N],c[N];
int tot,head[N];
struct node{
	int to,nxt;
}e[N];
il void add(int u,int v){
	e[++tot]={v,head[u]},head[u]=tot;
}
struct SGT{
	int cur,ls[M],rs[M];
	ll tr[M][2];
	il void reset(int o,ll x,ll y){
		tr[o][0]+=x,tr[o][1]+=y;
	}
	il void pushdown(int o){
		if(!tr[o][0]&&!tr[o][1]){
			return;
		}
		if(!ls[o]){
			ls[o]=++cur;
		sum++;
		}
		if(!rs[o]){
			rs[o]=++cur;
		sum++;
		}
		reset(ls[o],tr[o][0],tr[o][1]);
		reset(rs[o],tr[o][0],tr[o][1]);
		tr[o][0]=tr[o][1]=0;
	}
	void merge(int l,int r,int &o,int u){
		if(!o||!u){
			o|=u;
			return;
		}
		tr[o][0]+=tr[u][0],tr[o][1]+=tr[u][1];
		int mid=(l+r)>>1;
		merge(l,mid,ls[o],ls[u]);
		merge(mid+1,r,rs[o],rs[u]);
	}
	ll query(int l,int r,int o,int x){
		if(l==r){
			return 1ll*tr[o][1]*x+tr[o][0];
		}
		int mid=(l+r)>>1;
		if(x<=mid){
			if(ls[o]){
				pushdown(o);
				return query(l,mid,ls[o],x);
			}
			return 1ll*tr[o][1]*x+tr[o][0];
		}
		if(rs[o]){
			pushdown(o);
			return query(mid+1,r,rs[o],x);
		}
		return 1ll*tr[o][1]*x+tr[o][0];
	}
	void updateA(int l,int r,int &o,int x,int y,int a,int b){
		if(x>y)return;
		if(!o){
			o=++cur;
		}
		if(l>=x&&r<=y){
			reset(o,a,b);
			return;
		}
		pushdown(o);
		int mid=(l+r)>>1;
		if(x<=mid){
			updateA(l,mid,ls[o],x,y,a,b);
		}
		if(y>mid){
			updateA(mid+1,r,rs[o],x,y,a,b);
		}
	}
	void updateR(int l,int r,int &o,int x,int y){
		if(x>y)return;
		if(!o){
			return;
		}
		if(l>=x&&r<=y){
			o=0;
			return;
		}
		pushdown(o);
		int mid=(l+r)>>1;
		if(x<=mid){
			updateR(l,mid,ls[o],x,y);
		}
		if(y>mid){
			updateR(mid+1,r,rs[o],x,y);
		}
	}
}T;
void dfs(int u,int f){
	go(i,u){
		int v=e[i].to;
		dfs(v,u);
		T.merge(1,k,rt[u],rt[v]);
	}
	if(u==1){
		return;
	}
	int l=1,r=k,ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(c[u]+T.query(1,k,rt[u],mid)>=1ll*a[u]*mid){
			l=(ans=mid)+1;
		}else{
			r=mid-1;
		}
	}
	T.updateR(1,k,rt[u],1,ans);
	T.updateA(1,k,rt[u],1,ans,0,a[u]);
	T.updateA(1,k,rt[u],ans+1,k,c[u],0);
}
void Yorushika(){
	scanf("%d%d",&n,&m);
	rep(i,2,n){
		int u=read();c[i]=read(),a[i]=read();
		add(u,i);
	}
	dfs(1,0);
	rep(i,1,m){
		int x=read();
		write(T.query(1,k,rt[1],x)),pc('\n');
	}
}
bool Med;
signed main(){
	cerr<<(&Mbe-&Med)/1048576.0;
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}