记录编号	494005	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]复仇的序幕曲	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	3.012 s
提交时间	2018-04-07 23:14:27	内存使用	5.43 MiB

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=80010;
struct poi{int u,w;};
struct shi{int len,x;};
vector<poi>p[maxn];
vector<shi>q[maxn][3];
int n,m,cnt,root,Sum,a[maxn],fa[maxn],Fa[maxn],sz[maxn];
int dep[maxn],son[maxn],top[maxn],dis[maxn],siz[maxn];
bool vis[maxn];
bool cmp(const shi&a,const shi&b){return a.len<b.len;}
inline void dfs1(int x){
	siz[x]=1;
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i].u,w=p[x][i].w;
		if(u==fa[x])continue;
		fa[u]=x,dep[u]=dep[x]+1,dis[u]=dis[x]+w;
		dfs1(u);
		siz[x]+=siz[u];
		if(siz[u]>siz[son[x]])son[x]=u;
	}
}
inline void dfs2(int x,int y){
	top[x]=y;
	if(!son[x])return;
	dfs2(son[x],y);
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i].u;
		if(u==son[x]||u==fa[x])continue;
		dfs2(u,u);
	}
}
int lca(int x,int y){
	int f1=top[x],f2=top[y];
	while(f1!=f2){
		if(dep[f1]<dep[f2])swap(x,y),swap(f1,f2);
		x=fa[f1],f1=top[x];
	}
	if(dep[x]>dep[y])swap(x,y);
	return x;
}
inline void getroot(int x,int fa){
	sz[x]=0;
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i].u;
		if(vis[u]||u==fa)continue;
		getroot(u,x);
		sz[x]=max(sz[x],siz[u]);
	}
	sz[x]=max(sz[x],Sum-siz[x]);
	if(sz[x]<sz[root])root=x;
}
inline void build(int x){
	vis[x]=1;
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i].u;
		if(vis[u])continue;
		Sum=siz[u],root=0,getroot(u,0);
		Fa[root]=x,build(root);
	}
}
int dist(int x,int y){return dis[x]+dis[y]-dis[lca(x,y)]*2;}
inline void insert(int x,int v){
	q[x][0].push_back((shi){0,v});
	for(int u=x;Fa[u];u=Fa[u]){
		int h=Fa[u],d=dist(x,h);
		q[u][1].push_back((shi){d,v});
		q[h][0].push_back((shi){d,v});
	}
}
int upper_bound(int x,int y,int k){
	int mid,ans=0,l=0,r=(int)q[x][y].size()-1;
	while(l<=r){
		mid=(l+r)>>1;
		if(q[x][y][mid].len<=k)ans=q[x][y][mid].x,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
inline void work(int x,int v){
	int ans=upper_bound(x,0,v);
	for(int u=x;Fa[u];u=Fa[u]){
		int h=Fa[u],d=dist(x,h);
		ans-=upper_bound(u,1,v-d);
		ans+=upper_bound(h,0,v-d);
	}
	printf("%d\n",ans);
}
int main(){
	freopen("SS.in","r",stdin);
	freopen("SS.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int x,y,w;
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&w);
		p[x].push_back((poi){y,w});
		p[y].push_back((poi){x,w});
	}
	sz[0]=Sum=n;
	dfs1(1);dfs2(1,1);getroot(1,0);build(root);
	for(int i=1;i<=n;i++)insert(i,a[i]);
	for(int i=1;i<=n;i++){
		sort(q[i][0].begin(),q[i][0].end(),cmp);
		sort(q[i][1].begin(),q[i][1].end(),cmp);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<(int)q[i][0].size();j++)
			q[i][0][j].x+=q[i][0][j-1].x;
		for(int j=1;j<(int)q[i][1].size();j++)
			q[i][1][j].x+=q[i][1][j-1].x;
	}
	while(m--){
		scanf("%d%d",&x,&y);
		work(x,y);
	}
	return 0;
}