rt,为什么大家都 Wa on #11 呀
#include<cstdio>
#include<algorithm>
#define INF (0x3f3f3f3f)
using namespace std;
const int MAXN = 1000005;
int n, Q;
int K, p[MAXN], num;
int root;
bool mark[MAXN];
class Graph {
private :
struct edge {
int to, nex;
}e[MAXN << 1]; int idx;
public :
int head[MAXN];
inline void add(int u, int v) {
e[++ idx].to = v;
e[idx].nex = head[u];
head[u] = idx;
}
inline void add_edge(int u, int v) {
add(u, v); add(v, u);
}
inline edge operator [] (const int &x) const {
return e[x];
}
inline void Clear() {
for (int i = 1; i <= idx; ++ i)
e[i].nex = 0;
idx = 0;
}
}G, T;
namespace Tree_Init {
int dep[MAXN], fa[MAXN][23];
int cnt_dfn, dfn[MAXN];
inline void Init_dfs(int u) {
dfn[u] = ++ cnt_dfn;
if (u == 1) dep[u] = 1;
for (int i = 1; i <= 20; ++ i)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (int i = G.head[u]; i; i = G[i].nex) {
int v = G[i].to;
if (v == fa[u][0]) continue;
dep[v] = dep[u] + 1;
fa[v][0] = u;
Init_dfs(v);
}
}
inline int Get_Lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = 20; ~i; -- i)
if (dep[fa[u][i]] >= dep[v])
u = fa[u][i];
if (u == v) return u;
for (int i = 20; ~i; -- i)
if (fa[u][i] != fa[v][i])
u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
}
using namespace Tree_Init;
namespace Build_Virtua_tree {
int top, stc[MAXN];
inline bool cmp(const int &x, const int &y) {
return dfn[x] < dfn[y];
}
inline int Build() {
T.Clear();
stc[top = 1] = p[1];
int lca;
for (int i = 2; i <= K; ++ i) {
lca = Get_Lca(p[i], stc[top]);
if (!mark[lca]) p[++ num] = lca;
while (true) {
if (dep[lca] >= dep[stc[top - 1]]) {
if (lca != stc[top]) {
T.add_edge(lca, stc[top]);
if (lca != stc[top - 1])
stc[top] = lca;
else -- top;
}
break;
} else{
T.add_edge(stc[top], stc[top - 1]);
-- top;
}
}
stc[++ top] = p[i];
}
while (-- top) T.add_edge(stc[top], stc[top + 1]);
return stc[1];
}
}
using namespace Build_Virtua_tree;
inline int dfs(int u, int fath, int &fg) {
int cts = 0, isd, res = 0;
for (int i = T.head[u]; i; i = T[i].nex) {
int v = T[i].to;
if (v == fath) continue;
isd = 0; res += dfs(v, u, isd);
cts += (isd == 0);
}
if (mark[u]) return res + cts;
if (cts <= 1) return res;
return fg = 1, res + 1;
}
inline void Clear_() {
for (int i = 1; i <= num; ++ i)
mark[p[i]] = false,
T.head[p[i]] = 0;
}
int main()
{
scanf ("%d", &n);
for (int i = 1; i < n; ++ i) {
int u, v;
scanf ("%d%d", &u, &v);
G.add_edge(u, v);
}
Init_dfs(1);
scanf ("%d", &Q);
while (Q --) {
scanf ("%d", &K);
for (int i = 1; i <= K; ++ i)
scanf ("%d", p + i), mark[p[i]] = true;
sort(p + 1, p + K + 1, cmp);
bool fg = false;
for (int i = 1; i <= K; ++ i)
if (mark[fa[p[i]][0]]) {
fg = true;
puts("-1");
break;
}
if (fg) {
Clear_();
continue;
}
num = K;
root = Build();
int t = 0;
printf ("%d\n", dfs(root, 0, t));
Clear_();
}
return 0;
}