C++11(clang++ 3.9) 解法, 执行用时: 456ms, 内存消耗: 33424K, 提交时间: 2019-08-01 21:58:07

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
std::vector<pair<int,int> > G[maxn];
int n,x,q,k;ll dis[maxn],sum[maxn];
int sz[maxn],fa[maxn];
inline void dfs(int u)
{
	sz[u]=1;
	for(auto &it:G[u])
	{
		int v,w;tie(v,w)=it;
		if(v==fa[u])continue;
		fa[v]=u;
		dis[v]=dis[u]+w;
		dfs(v);
		sz[u]+=sz[v];
		sum[u]+=sum[v]+sz[v]*w;
	}
}
inline ll solve(int u)
{
	queue<int>q;
	while(!q.empty())q.pop();
	ll ans=0;
	q.emplace(u);
	while(!q.empty())
	{
		u=q.front();q.pop();
		if(dis[u]-dis[x]>=k)
		{
			ans+=sz[u]*(dis[u]-dis[x])+sum[u];
			continue;
		}
		for(auto &it:G[u])
		{
			int v,w;tie(v,w)=it;
			if(v==fa[u])continue;
			q.emplace(v);
		}
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,w;scanf("%d%d",&u,&w);
		G[u].emplace_back(i+1,w);
		G[i+1].emplace_back(u,w);
	}
	dfs(1);
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d%d",&x,&k);
		printf("%lld\n",solve(x));
	}
	return 0;
}