Description：

一棵树，多次询问，给出 $m$ 个点，求有几个点到每个给定点最近。

$1\leqslant n,q,\sum m\leqslant 3\times 10^5$

Solution：

太神了只能抄题解，先把每次给出的虚树建出来，然后问题变成了怎么 $DP$ ，首先在虚树上两遍树形 $DP$ 求出虚树上每个点属于那个点，首先如果是标记点就已经确定好了，如果不是，在第一遍中选一个离他最近的在它子树中的标记点，第二遍在他的祖先中选，有点类似二次扫描加换根，然后再对这棵虚树的每条边 $(f,u)$ 分情况讨论，如果它两边都属于一个关键点，那么就可以倍增找到父亲在原树中的儿子，然后为这个关键点累加 $siz[son]-siz[u]$ 的贡献，如果属于不同的，就在树上倍增出分界点，然后分两部分累加贡献，最后还剩一些点没有在上述讨论中出现，他们一定是虚树的节点的子树，还有虚树的根上面那部分，他们的归属比较显然，但注意细节。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 300010

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

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

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

int f[MAXN][23],dep[MAXN],siz[MAXN],dfn[MAXN],tot = 0;

void dfs(int k,int depth)

{

	dep[k] = depth;dfn[k] = ++tot;siz[k] = 1;

	for(int i = 1;(1 << i) <= depth;++i)f[k][i] = f[f[k][i - 1]][i - 1];

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

	{

		if(e[i].to != f[k][0])

		{

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

			dfs(e[i].to,depth + 1);

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

		}

	}

	return;

}

int LCA(int a,int b)

{

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

	for(int k = 22;k >= 0;--k)if(dep[f[a][k]] >= dep[b])a = f[a][k];

	if(a == b)return a;

	for(int k = 22;k >= 0;--k)if(f[a][k] != f[b][k])a = f[a][k],b = f[b][k];

	return f[a][0];

}

int dist(int a,int b)

{

	if(a == 0 || b == 0)return 0x3f3f3f3f; 

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

}

int c[MAXN],s[MAXN],tp = 0,root,belong[MAXN];

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

bool vis[MAXN];

pair<int,int> p[MAXN];

void dfs1(int k)

{

	if(belong[k] != 0)p[k] = make_pair(0,k);

	else p[k] = make_pair(0x3f3f3f3f,0);

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

	{

		dfs1(e[i].to);

		p[k] = min(p[k],make_pair(dist(p[e[i].to].second,k),p[e[i].to].second));

	}

	return;

}

void dfs2(int k)

{

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

	{

		p[e[i].to] = min(p[e[i].to],make_pair(dist(e[i].to,p[k].second),p[k].second));

		dfs2(e[i].to);

	}

	return;

}

int mem[MAXN],ans[MAXN];

int skip_to_son(int st,int fa)

{

	for(int k = 22;k >= 0;--k)if(dep[f[st][k]] > dep[fa])st = f[st][k];

	return st;

}

int skip_by_dis(int st,int dis)

{

	for(int k = 22;k >= 0;--k)if(dis & (1 << k))st = f[st][k];

	return st;

}

void calc(int f,int u)

{

	if(dep[f] + 1 == dep[u])

	{

		ans[p[f].second] -= siz[u];

		return;

	}

	if(p[f].second == p[u].second)

	{

		ans[p[f].second] -= siz[u];

	}

	else

	{

		int dis = dist(p[f].second,p[u].second);

		int mid = skip_by_dis(p[u].second,dis / 2);

		if(dis % 2 == 0 && p[f].second < p[u].second)mid = skip_to_son(u,mid);

		ans[p[u].second] += siz[mid] - siz[u];

		ans[p[f].second] -= siz[mid];

	}

	return;

}

void dp(int k)

{

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

	{

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

		dp(e[i].to);

	}

	return;

}

int pnt[MAXN];

void calc()

{

	scanf("%d",&c[0]);

	for(int i = 1;i <= c[0];++i)scanf("%d",&c[i]);

	for(int i = 1;i <= c[0];++i)pnt[i] = c[i];

	for(int i = 1;i <= c[0];++i)belong[c[i]] = c[i];

	sort(c + 1,c + 1 + c[0],cmp);

	s[tp = 1] = c[1];

	mem[mem[0] = 1] = c[1]; 

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

	{

		int lca = LCA(s[tp],c[i]);

		if(lca == s[tp])

		{

			s[++tp] = c[i];

			mem[++mem[0]] = c[i];

			continue;

		}

		while(tp >= 2)

		{

			if(dfn[lca] < dfn[s[tp - 1]])

			{

				add(s[tp - 1],s[tp]);

				--tp;

			}

			else

			{

				add(lca,s[tp]);

				--tp;

				break;

			}

		}

		if(tp == 1 && dfn[lca] < dfn[s[tp]])

		{

			add(lca,s[tp]);

			s[tp] = lca;

			mem[++mem[0]] = lca;

		}

		if(lca != s[tp])

		{

			s[++tp] = lca;

			mem[++mem[0]] = lca;

		}

		s[++tp] = c[i];mem[++mem[0]] = c[i];

	}

	while(tp >= 2)

	{

		add(s[tp - 1],s[tp]);

		--tp;

	}

	root = s[tp];

	dfs1(root);

	dfs2(root);

	for(int k = 1;k <= mem[0];++k)ans[p[mem[k]].second] += siz[mem[k]];

	dp(root);

	ans[p[root].second] += siz[1] - siz[root];

	for(int i = 1;i <= c[0];++i)

	{

		printf("%d",ans[pnt[i]]);

		if(i == c[0])puts("");

		else putchar(' ');

	}

	for(int i = 1;i <= mem[0];++i)belong[mem[i]] = lin[mem[i]] = ans[mem[i]] = 0;

	edgenum = 0;

	return;

}

int main()

{

	scanf("%d",&n);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);add(b,a);

	}

	dfs(1,1);

	edgenum = 0;

	memset(lin,0,sizeof(lin));

	scanf("%d",&m);

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

	return 0;

}