WA on #11,不知道哪里挂了,求调
查看原帖
WA on #11,不知道哪里挂了,求调
464528
见贤思齐_Seakies楼主2023/8/2 21:46
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e6 + 9;
inline int read() {
	int X = 0; bool flag = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') flag = 0; ch = getchar();}
	while (ch >= '0' && ch <= '9') {X = (X << 1) + (X << 3) + ch - '0'; ch = getchar();}
	if (flag) return X;
	return ~(X - 1);
}
inline void write(int X) {
	if (X < 0) {X = ~(X - 1); putchar('-');}
	if (X > 9) write(X / 10);
	putchar(X % 10 + '0');
}
int n, m, k;
vector<int> g[MAXN];
int fa[MAXN], dep[MAXN], sz[MAXN], big[MAXN];
void dfs1(int u, int f) {
    fa[u] = f, dep[u] = dep[f] + 1, sz[u] = 1;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == f) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (!big[u] || sz[big[u]] < sz[v]) big[u] = v;
    }
}
int tot, tp[MAXN], dfn[MAXN];
void dfs2(int u, int t) {
    tp[u] = t, dfn[u] = ++tot;
    if (big[u]) dfs2(big[u], t);
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa[u] || v == big[u]) continue;
        dfs2(v, v);
    }
}
int lca(int x, int y) {
    while (tp[x] != tp[y]) {
        if (dep[tp[x]] < dep[tp[y]]) swap(x, y);
        x = fa[tp[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return x;
}
int q[MAXN];
bool vis[MAXN];
bool cmp(int x, int y) {
    return dfn[x] < dfn[y];
}
int s[MAXN], top;
struct Edge {
    int to, nxt;
} e[MAXN];
int h[MAXN], cnt;
void addedge(int u, int v) {
    e[cnt].to = v, e[cnt].nxt = h[u], h[u] = cnt++;
}
int siz[MAXN], ans;
void dp(int u) {
    if (siz[u]) {
        for (int i = h[u]; ~i; i = e[i].nxt) {
            int v = e[i].to;
            dp(v);
            if (siz[v]) ans++, siz[v] = 0;
        }
    } else {
        for (int i = h[u]; ~i; i = e[i].nxt) {
            int v = e[i].to;
            dp(v);
            siz[u] += siz[v];
            siz[v] = 0;
        }
        if (siz[u] > 1) siz[u] = 0, ans++;
    }
    h[u] = -1;
}
signed main() {
    n = read();
    for (int i = 1; i < n; i++) {
        int u, v;
        u = read(), v = read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    m = read();
    memset(h, -1, sizeof(h));
    while (m--) {
        ans = 0;
        cnt = 0;
        k = read();
        for (int i = 1; i <= k; i++) {
            q[i] = read();
            vis[q[i]] = true;
        }
        bool flag = false;
        for (int i = 1; i <= k; i++) {
            siz[q[i]] = 1;
            if (vis[fa[q[i]]]) {
                flag = true;
                break;
            }
        }
        if (flag) {
            puts("-1");
            for (int i = 1; i <= k; i++)
                siz[q[i]] = 0, vis[q[i]] = false;
            continue;
        }
        sort(q + 1, q + k + 1, cmp);
        tot = 0;
        s[top = 1] = 1;
        if (q[1] != 1) s[++top] = q[1];
        for (int i = 2; i <= k; i++) {
            int l = lca(s[top], q[i]);
            while (top > 1 && dep[s[top - 1]] >= dep[l]) {
                addedge(s[top - 1], s[top]);
                top--;
            }
            if (l != s[top]) addedge(l, s[top]), s[top] = l;
            s[++top] = q[i];
        }
        while (top) addedge(s[top - 1], s[top]), top--;
        dp(1);
        write(ans); puts("");
        for (int i = 1; i <= k; i++)
            siz[q[i]] = 0, vis[q[i]] = false;
    }
    return 0;
}
2023/8/2 21:46
加载中...