记录编号	252785	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]复仇的序幕曲	最终得分	100
用户昵称	Aglove	是否通过	通过
代码语言	C++	运行时间	2.434 s
提交时间	2016-04-21 07:03:21	内存使用	14.10 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long LL;
const int maxn=100010;
const int oo=0x7fffffff;
int n,m,g,sum,id,ff,sz,t;
int u,v,b,mx,k;
int a[maxn];
int h[maxn],cnt=0;
struct edge{
	int to,next,w;
}G[maxn<<1];
int dep[maxn],dis[maxn],anc[maxn][20];
int f[maxn],w[maxn],fa[maxn],d[maxn];
bool vis[maxn];
LL ans=0;
struct pos{
	int dis;LL s;
	pos(int dis=0,LL s=0):dis(dis),s(s){}
};
vector<pos>V[maxn];
vector<pos>F[maxn];
void cmax(int &a,int b){if(b>a)a=b;}
bool cmp(const pos &A,const pos &B){return A.dis<B.dis;}
void add(int x,int y,int z){
	++cnt;G[cnt].to=y;G[cnt].next=h[x];G[cnt].w=z;h[x]=cnt;
}
void read(int &num){
	num=0;char ch=getchar();
	while(ch<'!')ch=getchar();
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
void DFS(int u,int f){
	anc[u][0]=f;
	for(int i=h[u];i;i=G[i].next){
		int v=G[i].to;
		if(v==f)continue;
		dep[v]=dep[u]+1;
		dis[v]=dis[u]+G[i].w;
		DFS(v,u);
	}return;
}
void pre_LCA(){
	for(int i=1;i<=n;++i){
		for(int j=1;(1<<j)<=n;++j)anc[i][j]=-1;
	}
	for(int j=1;(1<<j)<=n;++j){
		for(int i=1;i<=n;++i){
			if(anc[i][j-1]!=-1){
				int a=anc[i][j-1];
				anc[i][j]=anc[a][j-1];
			}
		}
	}return;
}
int LCA(int p,int q){
	if(dep[p]<dep[q]){t=p;p=q;q=t;}
	int log;
	for(log=0;(1<<log)<=dep[p];++log);--log;
	for(int i=log;i>=0;--i){
		if(dep[p]-(1<<i)>=dep[q])p=anc[p][i];
	}
	if(p==q)return p;
	for(int i=log;i>=0;--i){
		if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){
			p=anc[p][i];q=anc[q][i];
		}
	}return anc[p][0];
}
int dist(int u,int v){return dis[u]+dis[v]-2*dis[LCA(u,v)];}
void Get_G(int u,int fa){
	f[u]=0;w[u]=1;
	for(int i=h[u];i;i=G[i].next){
		int v=G[i].to;
		if(v==fa||vis[v])continue;
		Get_G(v,u);
		w[u]+=w[v];cmax(f[u],w[v]);
	}cmax(f[u],sum-w[u]);
	if(f[u]<f[g])g=u;
}
void Get_dis(int u,int f){
	V[id].push_back(pos(d[u],a[u]));
	if(ff!=-1)F[id].push_back(pos(dist(u,ff),a[u]));
	for(int i=h[u];i;i=G[i].next){
		int v=G[i].to;
		if(vis[v]||v==f)continue;
		d[v]=d[u]+G[i].w;
		Get_dis(v,u);
	}return;
}
void Get_div(int u,int f){
	fa[u]=f;vis[u]=true;
	id=u;ff=f;d[u]=0;Get_dis(u,-1);
	for(int i=h[u];i;i=G[i].next){
		int v=G[i].to;
		if(vis[v])continue;
		g=0;sum=w[v];
		Get_G(v,u);Get_div(g,u);
	}return;
}
LL Get_pos(vector<pos>&V){
	int L=0,R=V.size()-1;
	if(V[0].dis>k)return 0;
	while(L<R){
		int mid=L+((R-L+1)>>1);
		if(V[mid].dis<=k)L=mid;
		else R=mid-1;
	}return V[L].s;
}
void ask(int u,int v){
	int R;LL now,D;
	D=dist(u,v);
	k-=D;now=Get_pos(V[u]);k+=D;
	ans+=now;
	if(fa[u]==-1)return;
	D=dist(fa[u],v);
	k-=D;now=Get_pos(F[u]);k+=D;
	ans-=now;
	ask(fa[u],v);
}

int main(){
	freopen("SS.in","r",stdin);
	freopen("SS.out","w",stdout);
	read(n);read(m);
	for(int i=1;i<=n;++i)read(a[i]);
	for(int i=1;i<n;++i){
		read(u);read(v);read(b);
		add(u,v,b);add(v,u,b);
	}
	DFS(1,-1);pre_LCA();
	g=0;sum=n;f[0]=oo;
	Get_G(1,-1);Get_div(g,-1);
	for(int i=1;i<=n;++i){
		sort(V[i].begin(),V[i].end(),cmp);
		sz=V[i].size();
		for(int j=1;j<sz;++j)V[i][j].s+=V[i][j-1].s;
		sort(F[i].begin(),F[i].end(),cmp);
		sz=F[i].size();
		for(int j=1;j<sz;++j)F[i][j].s+=F[i][j-1].s;
	}
	while(m--){
		read(u);read(k);
		ans=0;
		ask(u,u);
		printf("%lld\n",ans);
	}return 0;
	
}