rt,#1~#10 全 MLE,问题目前出在 dfs1 时跳不出来循环导致的爆空间。
bool _Start;
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<cmath>
#include<unordered_map>
using namespace std;
char buf[1<<20], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=buf+fread(p1=buf, 1, 1<<20, stdin), p1==p2)?EOF:*p1++)
template <typename T>
void read(T &x)
{
x=0;int f=1;char c=getchar();
while (!isdigit(c)) f=(c=='-')?-1:1, c=getchar();
while (isdigit(c)) x=(x<<1)+(x<<3)+c-'0', c=getchar();
x*=f;
}
typedef long long LL;
const int N=2e5+10;
const int inf=2e9;
int n, m, tsp, q[N], lg, ans[N], b[N];
struct edge{int x, y, pre;}a[N<<1];int alen, last[N<<1];
void ins(int x, int y)
{
alen++;a[alen]={x, y, last[x]};last[x]=alen;
alen++;a[alen]={y, x, last[y]};last[y]=alen;
}
edge G[N<<1];int glen, last_g[N<<1];
void ins_g(int x, int y)
{
glen++;G[glen]={x, y, last_g[x]};last_g[x]=glen;
glen++;G[glen]={y, x, last_g[y]};last_g[y]=glen;
}
int fa[N][19], dfn[N], dep[N], Size[N], stack[N], top;
bool cmp(int n1, int n2) {return dfn[n1]<dfn[n2];}
void init(int x, int f)
{
dfn[x]=++tsp, Size[x]=1, fa[x][0]=f;
for (int i=1;i<=lg;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for (int k=last[x];k;k=a[k].pre)
{
int y=a[k].y;
if (y==f) continue;
dep[y]=dep[x]+1;
init(y, x);Size[x]+=Size[y];
}
}
int LCA(int x, int y)
{
if (dep[x]<dep[y]) swap(x, y);
for (int i=lg;i>=0;i--)
if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if (x==y) return y;
for (int i=lg;i>=0;i--)
if (fa[x][i]!=fa[y][i]) x=fa[x][i], y=fa[y][i];
return fa[x][0];
}
int f[N], g[N];bool v[N];
void query(int x, int y)
{
int p=y, q=y;
for (int i=lg;i>=0;i--)
if (dep[fa[p][i]]>=dep[x]) p=fa[p][i];
for (int i=lg;i>=0;i--)
{
int l=dep[y]-dep[fa[q][i]]+f[y], r=dep[fa[q][i]]-dep[x]+f[x];
if (dep[fa[q][i]]>dep[x]&&(l<r||(l==r&&g[y]<g[x]))) q=fa[q][i];
}
ans[g[y]]+=Size[q]-Size[y];ans[g[x]]-=Size[q];
}
void dfs1(int x, int ff)
{
f[x]=inf;
for (int k=last_g[x];k;k=G[k].pre)
{
int y=G[k].y, val=dep[y]-dep[x];
if (y==ff) continue;
dfs1(y, x);
if (f[x]>f[y]+val) f[x]=f[y]+val, g[x]=g[y];
else if (f[y]+val==f[x]) g[x]=min(g[x], g[y]);
}
if (v[x]) f[x]=0, g[x]=x;
}
void dfs2(int x, int ff)
{
for (int k=last_g[x];k;k=G[k].pre)
{
int y=G[k].y, val=dep[y]-dep[x];
if (y==ff) continue;
if (f[x]+val<f[y]) f[y]=f[x]+val, g[y]=g[x];
else if (f[x]+val==f[y]) g[y]=min(g[x], g[y]);
query(x, y);
dfs2(y, x);
}
ans[g[x]]+=Size[x];
v[x]=last_g[x]=0;
}
bool _End;
int main()
{
// fprintf(stderr,"Memory: %.4lf Mib\n",abs(&_End-&_Start)/1048576.0);
freopen("P3233_1.in", "r", stdin);
memset(last_g, 0, sizeof last_g);
read(n);lg=log2(n);
for (int i=1;i<n;i++)
{
int x, y;
read(x), read(y);
ins(x, y);
}
read(m);
dep[1]=1;init(1, 0);
for (int t=1;t<=m;t++)
{
int k;read(k);glen=0;
for (int i=1;i<=k;i++) read(q[i]), b[i]=q[i], v[q[i]]=1, ans[q[i]]=0;
sort(q+1, q+k+1, cmp);stack[top=1]=1;
if (q[1]!=1) stack[++top]=q[1];
for (int i=2;i<=k;i++)
{
int lca=LCA(q[i], stack[top]);
while (top>1&&dep[stack[lca]]<dep[stack[top-1]]) ins_g(stack[top-1], stack[top]), top--;
if (lca!=stack[top])
{
ins_g(lca, stack[top]);
if (lca==stack[top-1]) top--;
else stack[top]=lca;
}
stack[++top]=q[i];
}
while (top>1) ins_g(stack[top-1], stack[top]), top--;
dfs1(1, 0);dfs2(1, 0);
for (int i=1;i<=k;i++)
printf("%d ", ans[b[i]]);
puts("");
}
return 0;
}