RT,静态查错后发现应该是建虚树和计算答案的问题,但就是查不出来,WA on #4 wrong answer 1st numbers differ - expected: '2', found: '1'
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
template <typename T>
inline void read(T& r) {
r=0;bool w=0;
char ch=getchar();
while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
while(ch>='0'&&ch<='9') r=(r<<3)+(r<<1)+(ch^48), ch=getchar();
r=w?-r:r;
}
const int N=1e5+10;
#define pb(x,y) edge[x].push_back(y);
#define addstk(x) h[x]=0,stk[++tp]=x;//清空邻接表并入栈
int n,q,k,a[N],fg[N],tag[N],ans;
vector<int>edge[N];//原树边
int h[N],e[N<<1],ne[N<<1],idx;
int dfn[N],dep[N],size[N],son[N],fa[N],top[N],tim;//计算dfs序及lca
int stk[N],tp;//维护虚树
void dfs1(int u,int f){
dfn[u]=++tim;
fa[u]=f;size[u]=1;dep[u]=dep[f]+1;
for(int v:edge[u]){
if(v==f)continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])son[u]=v;
}
}
void dfs2(int u,int t){
top[u]=t;
if(son[u])dfs2(son[u],t);
for(int v:edge[u]){
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
int lca(int x,int y){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
void add(int a,int b){e[++idx]=b,ne[idx]=h[a],h[a]=idx;}
bool cmp(int a,int b){return dfn[a]<dfn[b];}
void build(){
tp=0;addstk(1);idx=0;
for(int i=1;i<=k;++i){
if(a[i]==1)continue;
int anc=lca(stk[tp],a[i]);
if(anc!=stk[tp]){
while(tp>1&&dfn[stk[tp-1]]>dfn[anc])add(stk[tp-1],stk[tp]),--tp;
if(stk[tp-1]==anc)add(anc,stk[tp--]);
else add(anc,stk[tp--]),addstk(anc);
}
addstk(a[i]);
}
while(tp>1)add(stk[tp-1],stk[tp]),--tp;
}
int dfs3(int u){
int cnt=0,ans=0;
for(int i=h[u];i;i=ne[i])ans+=dfs3(e[i]),cnt+=tag[e[i]];
if(fg[u])tag[u]=1,ans+=cnt;
else cnt>1?tag[u]=0,++ans:tag[u]=cnt;
return ans;
}
int main(){
#ifdef LOCAL
freopen("std.in","r",stdin);
freopen("my.out","w",stdout);
#endif
read(n);
for(int i=1,a,b;i<n;++i){
read(a),read(b);
pb(a,b);pb(b,a);
}
dfs1(1,0),dfs2(1,1);
read(q);
while(q--){
read(k);
for(int i=1;i<=k;++i)read(a[i]),fg[a[i]]=1;
bool fl=0;
for(int i=1;i<=k;++i)if(fg[fa[a[i]]]){fl=1;break;}
if(fl)printf("-1\n");
else {
sort(a+1,a+k+1,cmp);build();
printf("%d\n",dfs3(1));
}
for(int i=1;i<=k;++i)fg[a[i]]=0;
}
return 0;
}