제출 #1361836

#제출 시각아이디문제언어결과실행 시간메모리
1361836HishamAlshehriSpring cleaning (CEOI20_cleaning)C++20
0 / 100
85 ms24860 KiB
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
// using namespace __gnu_pbds;
 
#define int long long
#define mod 1000000007
#define base 7001
#define base2 757
#define F first
#define S second
// #define pi acos(-1)
#define double long double
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
// #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,sse3,sse4,avx")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

constexpr int maxn = 400001;
const int N = 1 << (int)(ceil(log2(maxn)));

int n, q, d[maxn], in[maxn], jump[18][maxn], parity[maxn], prf[maxn], tim, ans;
vector<int> adj[maxn], vrt[maxn];
bool vis[maxn];

int dfs(int v) {
    in[v] = tim++, vis[v] = 1;
    int num = 0;

    if (adj[v].size() == 1) num = 1;

    for (int u : adj[v]) {
        if (!vis[u]) {
            jump[0][u] = v;
            d[u] = d[v] + 1;
            int x = dfs(u);
            ans += x;
            num += x;
        }
    }

    parity[v] = (num % 2 ? 1 : -1);
    return 2 - num % 2;
}

void calc(int v, int cur) {
    vis[v] = 1, prf[v] = cur;

    for (int u : adj[v]) if (!vis[u]) calc(u, cur + parity[u]);
}

int rt = 1;

void build() {
    jump[0][rt] = rt;
    for (int i = 1; i < 18; i++) {
        for (int j = 1; j <= n; j++) jump[i][j] = jump[i - 1][jump[i - 1][j]];
    }
}

int lca(int v, int u) {
    if (v == u) return v;
    if (d[v] > d[u]) swap(u, v);

    int t = d[u] - d[v];

    for (int k = 17; k >= 0; k--) {
        if (((1 << k) & t)) u = jump[k][u];
    }

    for (int k = 17; k >= 0; k--) {
        if (jump[k][v] != jump[k][u]) v = jump[k][v], u = jump[k][u];
    }

    return jump[0][v];
}

int cnt;

int answer(int v) {
    int num = 0;
    for (int u : vrt[v]) {
        int x = dfs(u);
        if (x % 2) cnt += prf[u] - prf[v];
        num += x;
    }

    return num % 2;
}

signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> q;

    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);

        if (adj[v].size() > 1) rt = v;
    }

    int cccc = 0;

    for (int i = 1; i <= n; i++) {
        if (adj[i].size() == 1) cccc++;
    }

    dfs(rt);
    memset(vis, 0, sizeof vis);
    calc(rt, 0);
    memset(vis, 0, sizeof vis);
    build();

    while (q--) {
        int t; cin >> t;
        vector<pair<int, int>> v;
        int cc = cccc;
        for (int i = 0; i < t; i++) {
            int x; cin >> x;
            int cur = n + i + 1;
            jump[0][cur] = x, d[cur] = d[x] + 1, in[cur] = in[x];
            v.push_back({in[cur], cur});
            cc++;
            if (adj[x].size() == 1) cc--;
            cnt++;
        }

        if (cc % 2) {
            cout << "-1\n";
            continue;
        }

        for (int i = 1; i < 18; i++) {
            for (int j = n + 1; j <= n + t; j++) jump[i][j] = jump[i - 1][jump[i - 1][j]];
        }

        vis[rt] = 1;
        for (int i = 0; i < v.size() - 1; i++) {
            int x = v[i].S, y = v[i + 1].S;
            int w = lca(x, y);
            if (vis[w]) continue;
            vis[w] = 1;
            v.push_back({in[w], w});
        }
        v.push_back({0, rt});

        sort(v.begin(), v.end());

        vector<int> stck;
        stck.push_back(rt);
        for (int i = 1; i < v.size(); i++) {
            while (stck.size() && lca(stck.back(), v[i].S) != stck.back()) stck.pop_back();
            vrt[stck.back()].push_back(v[i].S);
            stck.push_back(v[i].S);
        }

        answer(rt);
        cout << cnt + ans << '\n';

        for (auto [_, i] : v) {
            vis[i] = 0;
            vrt[i].clear();
        }
        for (int i = n + 1; i <= n + t; i++) {
            for (int j = 0; j < 18; j++) jump[j][i] = 0;
            in[i] = d[i] = 0;
        }
        cnt = 0;
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…