Description：

给出一棵树，每次给出一个集合，元素 $(p,r)$ 表示标记了距离 $p$ 不超过 $r$ 的点，求出一共标记的多少点。

$1\leqslant n\leqslant 10^5$

Solution：

首先肯定会想到建虚树，把边拆点，这样对于虚树上的每条边到两端点距离相等的位置一定在某个点上，可以用动态点分治来求距离某个点不超过 $r$ 的点的个数，然后先一遍 $dfs$ 预处理出从虚树上每个点可以延伸出去的长度，然后把每个点统计的答案都加上，最后考虑虚树上的每条边有哪些点被重复计算了，倍增找到 $mid$ 使得两个边的端点在 $mid$ 这个点上具有相同的延伸长度，然后减掉重复的贡献即可。

Code：

#pragma GCC optimize("O2,Ofast,inline,unroll-all-loops,-ffast-math")

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

#pragma GCC optimaze(2)

using namespace std;

inline int rd()

{

	register int res = 0;register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res;

}

int n,m;

#define MAXN 100010

#define INF 0x3f3f3f3f

struct edge{int to,nxt;}e[MAXN << 1];

int edgenum = 0,lin[MAXN] = {0};

inline void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int dep[MAXN],dfn[MAXN],tot = 0;

namespace D

{

	int f[MAXN][16];

	inline int skip_to_dep(int k,int depth)

	{

		for(register int i = 15;i >= 0;--i)if(dep[f[k][i]] >= depth)k = f[k][i];

		return k;

	}

	inline int LCA(int a,int b)

	{

		if(dep[a] < dep[b])swap(a,b);

		a = skip_to_dep(a,dep[b]);

		if(a == b)return a;

		for(register int i = 15;i >= 0;--i)

			if(f[a][i] != f[b][i])a = f[a][i],b = f[b][i];

		return f[a][0];

	}

	inline int dis(int a,int b)

	{

		return dep[a] + dep[b] - 2 * dep[LCA(a,b)];

	}

}

void dfs(int k,int fa)

{

	dep[k] = dep[fa] + 1;

	dfn[k] = ++tot;

	for(register int i = 1;i <= 15;++i)

		D::f[k][i] = D::f[D::f[k][i - 1]][i - 1];

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		D::f[e[i].to][0] = k;

		dfs(e[i].to,k);

	}

	return;

}

#define pb push_back

namespace P

{

	vector<int> sum[MAXN],tofa[MAXN];

	int fa[MAXN];

	int root,s,siz[MAXN],d[MAXN];

	bool vis[MAXN];

	void getroot(int k,int fa)

	{

		siz[k] = 1;d[k] = 0;

		for(register int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(vis[e[i].to] || e[i].to == fa)continue;

			getroot(e[i].to,k);

			siz[k] += siz[e[i].to];

			d[k] = max(d[k],siz[e[i].to]);

		}

		d[k] = max(d[k],s - siz[k]);

		if(d[k] < d[root])root = k;

		return;

	}

	void divide(int k)

	{

		vis[k] = true;

		for(register int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(vis[e[i].to])continue;

			root = 0;s = siz[e[i].to];getroot(e[i].to,0);

			fa[root] = k;divide(root);

		}

		return;

	}

	vector<int> di[MAXN];

	inline void add(int k)

	{

		sum[k].pb(0);

		for(register int i = k;fa[i] != 0;i = fa[i])

		{

			register int dist = D::dis(k,fa[i]);

			sum[fa[i]].pb(dist);

			tofa[i].pb(dist);

		}

		return;

	}

	inline void get(int k)

	{

		for(register int i = k;fa[i] != 0;i = fa[i])di[k].pb(D::dis(k,fa[i]));

		return;

	}

	inline int count(int k,int r)

	{

		if(r == -1)return 0;if(r == 0)return 1; 

		register int ans = upper_bound(sum[k].begin(),sum[k].end(),r) - sum[k].begin();//cout << ans << endl;

		for(register int i = k,cur = 0;fa[i] != 0;i = fa[i],++cur)

		{

			ans += upper_bound(sum[fa[i]].begin(),sum[fa[i]].end(),r - di[k][cur]) - sum[fa[i]].begin();

			ans -= upper_bound(tofa[i].begin(),tofa[i].end(),r - di[k][cur]) - tofa[i].begin();

		}

		return ans;

	}

}

int p[MAXN],r[MAXN];

bool cmp_dfn(int a,int b){return dfn[a] < dfn[b];}

int stack[MAXN],top = 0;

vector<int> g[MAXN];

void dfs1(int k)

{

	for(register vector<int>::iterator it = g[k].begin();it != g[k].end();++it)

	{

		dfs1(*it);

		r[k] = max(r[k],r[*it] - (dep[*it] - dep[k]));

	}

	return;

}

long long ans;

void dp(int k)

{

	ans = ans + P::count(k,r[k]);//cout << k << " " << P::count(k,r[k]) << endl;

	for(register vector<int>::iterator it = g[k].begin();it != g[k].end();++it)

	{

		r[*it] = max(r[*it],r[k] - D::dis(k,*it));

		if(dep[*it] - dep[k] <= r[k] + r[*it])

		{

			register int mid = D::skip_to_dep(*it,(r[k] - r[*it] + dep[k] + dep[*it]) / 2);//cout << r[k] << " " << r[*it] << " " << r[k] - r[*it] << " " << dep[k] + dep[*it] << " " << (r[k] - r[*it] + dep[k] + dep[*it]) << endl;

			ans = ans - P::count(mid,r[k] - (dep[mid] - dep[k]));//cout << k << " -> " << *it << " " << mid << endl;

		}

		dp(*it);

	}

	r[k] = -1;

	g[k].clear();

	return;

}

int main()

{

	scanf("%d",&n);

	for(register int i = 1;i < n;++i)add(rd(),i + n),add(rd(),i + n);

	dfs(1,0);

	P::root = 0;P::s = n;P::d[0] = INF;

	P::getroot(1,0);P::divide(P::root);

	for(register int i = 1;i <= n;++i)P::add(i);

	for(register int i = 1;i <= n * 2 - 1;++i)

	{

		P::get(i);

		P::sum[i].pb(INF);P::tofa[i].pb(INF);

		sort(P::sum[i].begin(),P::sum[i].end());

		sort(P::tofa[i].begin(),P::tofa[i].end());

	}

	memset(r,-1,sizeof(r));

	scanf("%d",&m);

	for(register int i = 1;i <= m;++i)

	{

		p[0] = rd();

		for(register int k = 1;k <= p[0];++k){p[k] = rd();r[p[k]] = rd() * 2;}

		sort(p + 1,p + 1 + p[0],cmp_dfn);

		stack[top = 1] = p[1];

		for(register int i = 2;i <= p[0];++i)

		{

			register int lca = D::LCA(stack[top],p[i]);

			if(lca == stack[top]){stack[++top] = p[i];continue;}

			while(top >= 2)

			{

				if(dfn[lca] < dfn[stack[top - 1]]){g[stack[top - 1]].pb(stack[top]);--top;}

				else{g[lca].pb(stack[top]);--top;break;}

			}

			if(top == 1 && dfn[lca] < dfn[stack[1]]){g[lca].pb(stack[1]);stack[1] = lca;}

			if(stack[top] != lca)stack[++top] = lca;

			stack[++top] = p[i];

		}

		while(top >= 2)g[stack[top - 1]].pb(stack[top]),--top;

		dfs1(stack[1]);

		ans = 0;

		dp(stack[1]);

		printf("%lld\n",ans);

	}

	return 0;

}