RT,不知为何,感觉时间复杂度没问题
#include<bits/stdc++.h>
using namespace std;
#define ll long long
template <class T> inline void read(T &x)
{
x = 0;
int f = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
{
f |= ch == '-';
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + (ch - 48);
ch = getchar();
}
x = f ? -x : x;
return;
}
#define inf 0x3f3f3f3f
#define N 100005
struct Graph
{
int first[N], Next[N << 1], to[N << 1], w[N << 1], tot;
inline void add(int x, int y, int z)
{
Next[++tot] = first[x];
first[x] = tot;
to[tot] = y;
w[tot] = z;
return;
}
};
Graph Ori, Vir;
int n, q;
int dfn[N], sign, dep[N], fa[N][21];
void dfs(int u, int pre)
{
dfn[u] = ++sign;
for(int i = 1; (1 << i) <= dep[u]; i++)
{
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for(int i = Ori.first[u]; i; i = Ori.Next[i])
{
int v = Ori.to[i];
if(v == pre)
{
continue;
}
dep[v] = dep[u] + 1;
fa[v][0] = u;
dfs(v, u);
}
return;
}
int lca(int x, int y)
{
if(dep[x] > dep[y])
{
swap(x, y);
}
for(int i = 20; i >= 0; i--)
{
if(dep[fa[y][i]] >= dep[x])
{
y = fa[y][i];
}
}
if(x == y)
{
return x;
}
for(int i = 20; i >= 0; i--)
{
if(fa[x][i] != fa[y][i])
{
x = fa[x][i], y = fa[y][i];
}
}
return fa[x][0];
}
int a[N], st[N], top;
void build(int siz)
{
Vir.tot = 0;
st[top = 1] = 1;
for(int i = 1; i <= siz; i++)
{
int now = a[i], lc = lca(st[top], now);
while(1)
{
if(dep[lc] < dep[st[top - 1]])
{
Vir.add(st[top - 1], st[top], dep[st[top]] - dep[st[top - 1]]);
top--;
}
else if(dep[lc] < dep[st[top]])
{
Vir.add(lc, st[top], dep[st[top]] - dep[lc]);
top--;
}
else
{
break;
}
}
if(st[top] != lc)
{
st[++top] = lc;
}
if(st[top] != now)
{
st[++top] = now;
}
}
while(--top)
{
Vir.add(st[top], st[top + 1], dep[st[top + 1]] - dep[st[top]]);
}
return;
}
int col[N];
int f[N][2];
void dp(int u)
{
int tmp0 = 0, tmp1 = 0, ch = 0;
for(int i = Vir.first[u]; i; i = Vir.Next[i])
{
int v = Vir.to[i];
dp(v);
if((f[v][0] == inf && f[v][1] == inf) || (col[u] && col[v] && Vir.w[i] == 1))
{
f[u][0] = f[u][1] = inf;
Vir.first[u] = 0;
return;
}
if(f[v][0] <= f[v][1] + 1)
{
tmp0 += f[v][0];
}
else
{
ch++;
tmp0 += f[v][1];
}
tmp1 += f[v][1];
}
if(!col[u])
{
f[u][0] = min(tmp1 + 1, tmp0 + ch);
f[u][1] = tmp0 + ch - 1;
}
else
{
f[u][0] = inf;
f[u][1] = tmp0 + ch;
}
Vir.first[u] = 0;
return;
}
bool cmp(const int &a, const int &b)
{
return dfn[a] < dfn[b];
}
signed main()
{
read(n);
int u, v;
for(int i = 1; i < n; i++)
{
read(u), read(v);
Ori.add(u, v, 0), Ori.add(v, u, 0);
}
dep[1] = 1;
dfs(1, 0);
read(q);
int num;
while(q--)
{
read(num);
for(int i = 1; i <= num; i++)
{
read(a[i]);
col[a[i]] = 1;
}
sort(a + 1, a + num + 1, cmp);
build(num);
dp(1);
for(int i = 1; i <= num; i++)
{
col[a[i]] = 0;
}
int prtans = min(f[1][0], f[1][1]);
printf("%d\n", prtans == inf ? -1 : prtans);
}
return 0;
}