调了很久,CF 上 #29 一直 TLE,应该不是常数的问题。记录。
// LUOGU_RID: 91405805
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
#define il inline
const ll inf=1145141919810;
inline int Read()
{
int x = 0,f = 1;
char a = getchar();
while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
return x * f;
}
int n;
vector<int> E[300005];
int fa[300005],dfn[300005],dep[300005],siz[300005],hc[300005],tp[300005];
int cnt=0;
void dfs(int u){
dep[u]=dep[fa[u]]+1;siz[u]=1;hc[u]=-1;dfn[u]=++cnt;
for(auto v:E[u]){
siz[u]+=siz[v];
if(v==fa[u]) continue;
fa[v]=u;dfs(v);
if(hc[u]==-1 || siz[hc[u]]<siz[v]) hc[u]=v;
}
}
void dfs2(int u,int t){
tp[u]=t;
if(hc[u]!=-1) dfs2(hc[u],t);
for(auto v:E[u]){
if(v==fa[u] || v==hc[u]) continue;
dfs2(v,v);
}
}
int lca(int u,int v){
while(tp[u]!=tp[v]){
if(dep[tp[u]]<dep[tp[v]]) swap(u,v);
u=fa[tp[u]];
}
if(dep[u]<dep[v]) swap(u,v);
return v;
}
int m;
int p[300005];
bool vis[300005];
int t[300005],tot;
vector<int> S[300005];
int f[300005],g[300005];
bool cmp(int u,int v){ return dfn[u]<dfn[v]; }
bool cmpeq(int u,int v){ return dfn[u]==dfn[v]; }
void work(){
m=Read();
for(int i=1;i<=m;i++) p[i]=Read(),t[i]=p[i],vis[p[i]]=1;
tot=m;
sort(p+1,p+m+1,cmp);
for(int i=1;i<=m;i++) if(vis[fa[p[i]]]){
cout<<"-1\n";
for(int i=1;i<=m;i++) vis[p[i]]=0;
return;
}
for(int i=1;i<m;i++){
t[++tot]=lca(p[i],p[i+1]);
}
sort(t+1,t+tot+1,cmp);
tot=unique(t+1,t+tot+1,cmpeq)-t-1;
for(int i=2;i<=tot;i++){
S[lca(t[i-1],t[i])].push_back(t[i]);
}
for(int i=tot;i>=1;i--){
int u=t[i];int c=0;
// cout<<"KEY "<<u<<"\n";
g[u]=vis[u];f[u]=0;
for(auto v:S[u]){
// cout<<" SON"<<v<<"\n";
// if(vis[u] && vis[v]){ brk=1;break; }
f[u]+=f[v];
c+=g[v];
}
if(vis[u]){
f[u]+=c;
}else{
if(c>1) f[u]++;
else if(c==1) g[u]=1;
else g[u]=0;
}
// cout<<"-- RES "<<f[u]<<"\n";
}
printf("%d\n",f[t[1]]);
for(int i=1;i<=tot;i++) S[t[i]].clear();
for(int i=1;i<=m;i++) vis[p[i]]=0;
}
int main(){
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
n=Read();
for(int i=1;i<n;i++){
int u=Read(),v=Read();
E[u].push_back(v);
E[v].push_back(u);
}
dfs(1);dfs2(1,1);
int q=Read();
while(q--){
work();
}
return 0;
}