WA 在了 #11 的第 6 个,求各位 dalao 帮忙找一下 bug。qwq
#include<bits/stdc++.h>
using namespace std;
#define bmax(x,y) (dep[x]<dep[y] ? x : y)
vector<int> v[100100],vv[100100];
int dep[100100],id[100100],dfn[200100],cnt;
int st[200100][20];
bool isc[100100];
int ans=0;
bool cmp(const int x, const int y) { return id[x]<id[y]; }
void init(int x, int fa)
{
dfn[++cnt]=x; id[x]=cnt; dep[x]=dep[fa]+1;
for(int y : v[x])
if(y!=fa)
{
init(y, x);
dfn[++cnt]=x;
}
}
void initST()
{
for(int i=1; i<=cnt; i++) st[i][0]=dfn[i];
for(int j=1; j<20; j++)
for(int i=1; i+(1<<j)-1<=cnt; i++)
st[i][j]=bmax(st[i][j-1], st[i+(1<<j-1)][j-1]);
}
int LCA(int x, int y)
{
int l=id[x],r=id[y];
if(l>r) swap(l, r);
int t=log2(r-l+1);
return bmax(st[l][t], st[r-(1<<t)+1][t]);
}
void build(vector<int> b)
{
static int stk[100100],top;
sort(b.begin(), b.end(), cmp);
stk[top=1]=1;
for(int x : b)
if(x!=1)
{
int lca=LCA(x, stk[top]);
if(lca!=stk[top])
{
while(dfn[lca]<dfn[stk[top-1]])
{
vv[stk[top-1]].push_back(stk[top]);
--top;
}
vv[lca].push_back(stk[top]);
if(lca!=stk[top-1]) stk[top]=lca;
else --top;
}
stk[++top]=x;
}
for(int i=1; i<top; i++)
vv[stk[i]].push_back(stk[i+1]);
}
int dfs(int x)
{
int cnt=0;
for(int y : vv[x])
{
if(isc[y]&&isc[x]&&dep[y]-dep[x]==1) ans=-1e9;
cnt+=dfs(y);
}
vv[x].clear();
if(isc[x])
{
ans+=cnt;
return 1;
}
else if(cnt>1)
{
++ans;
return 0;
}
else
return cnt;
}
void work()
{
vector<int> b;
int n;
scanf("%d", &n);
for(int i=1; i<=n; i++)
{
int x;
scanf("%d", &x);
b.push_back(x); isc[x]=1;
}
ans=0;
build(b); dfs(1);
printf("%d\n", ans<0 ? -1 : ans);
for(int x : b) isc[x]=0;
}
int main()
{
int n,q;
cin>>n;
for(int i=1; i<n; i++)
{
int x,y;
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
cin>>q; init(1, 0); initST();
for(int i=1; i<=q; i++) work();
return 0;
}