Submission #1361826

#TimeUsernameProblemLanguageResultExecution timeMemory
1361826m5588ohammedSpring cleaning (CEOI20_cleaning)C++20
0 / 100
60 ms27200 KiB
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long

const int MAXN = 100005;
const int LOG = 20;

int n, q;
int depth[MAXN], t[LOG][MAXN];
int entry[MAXN], exsi[MAXN], siz[MAXN];
int ent = 0, exs = 0;
int Oans = 0;

array<int,2> pre[MAXN];

vector<int> v[MAXN], vr[MAXN];

int marked[MAXN];
int timerMark = 1;

bool is_ancestor(int a, int b){
    return entry[a] <= entry[b] && exsi[b] <= exsi[a];
}

int LCA(int a, int b){
    if(depth[a] < depth[b]) swap(a,b);

    int k = depth[a] - depth[b];

    for(int bt = LOG-1; bt >= 0; bt--){
        if(k >= (1LL << bt)){
            k -= (1LL << bt);
            a = t[bt][a];
        }
    }

    if(a == b) return a;

    for(int bt = LOG-1; bt >= 0; bt--){
        if(t[bt][a] != t[bt][b]){
            a = t[bt][a];
            b = t[bt][b];
        }
    }

    return t[0][a];
}

void dfs1(int i, int last){
    if((int)v[i].size() == 1) siz[i] = 1;

    for(int j : v[i]){
        if(j == last) continue;

        dfs1(j, i);
        siz[i] = (siz[i] + siz[j]) % 2;
    }

    if(i != 1){
        Oans += 2 - (siz[i] % 2);
    }
}

void dfs2(int i, int last){
    t[0][i] = last;
    depth[i] = depth[last] + 1;
    entry[i] = ent++;

    if(i == 1){
        pre[0][i] = 0;
        pre[1][i] = 0;
    }
    else{
        pre[0][i] = pre[0][last] + (1 - (siz[i] % 2));
        pre[1][i] = pre[1][last] + (siz[i] % 2);
    }

    for(int j : v[i]){
        if(j == last) continue;
        dfs2(j, i);
    }

    exsi[i] = exs++;
}

array<int,2> calc(int i, int last){
    array<int,2> ans = {0, 0};

    if(marked[i] == timerMark){
        ans[1] = 1;
    }

    for(int j : vr[i]){
        array<int,2> a = calc(j, i);
        ans[0] += a[0];
        ans[1] ^= a[1];
    }

    if(i != 1 && ans[1] == 1){
        ans[0] += (pre[1][i] - pre[1][last]) - (pre[0][i] - pre[0][last]);
    }

    return ans;
}

int answer_virtual(vector<int> leafs){
    timerMark++;

    vector<int> nodes;

    nodes.push_back(1);

    for(int x : leafs){
        marked[x] = timerMark;
        nodes.push_back(x);
    }

    sort(nodes.begin(), nodes.end(), [&](int a, int b){
        return entry[a] < entry[b];
    });

    int sz = nodes.size();

    for(int i = 1; i < sz; i++){
        nodes.push_back(LCA(nodes[i-1], nodes[i]));
    }

    sort(nodes.begin(), nodes.end(), [&](int a, int b){
        return entry[a] < entry[b];
    });

    nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());

    vector<int> st;

    for(int x : nodes){
        while(!st.empty() && !is_ancestor(st.back(), x)){
            st.pop_back();
        }

        if(!st.empty()){
            vr[st.back()].push_back(x);
        }

        st.push_back(x);
    }

    array<int,2> u = calc(1, 0);

    int ans = Oans + u[0];

    for(int x : nodes){
        vr[x].clear();
    }

    return ans;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;

    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;

        v[a].push_back(b);
        v[b].push_back(a);
    }

    dfs1(1, 0);
    dfs2(1, 0);

    for(int bt = 1; bt < LOG; bt++){
        for(int i = 1; i <= n; i++){
            t[bt][i] = t[bt-1][t[bt-1][i]];
        }
    }

    while(q--){
        int k;
        cin >> k;

        vector<int> vc(k);

        for(int i = 0; i < k; i++){
            cin >> vc[i];
        }

        if(k == 0){
            if(siz[1] % 2 == 1){
                cout << -1 << endl;
            }
            else{
                cout << Oans << endl;
            }
            continue;
        }

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

        vector<int> leafs;
        int cnt = 0;

        for(int i = 0; i < k; ){
            int x = vc[i];
            int j = i;

            while(j < k && vc[j] == x){
                j++;
            }

            int fre = j - i;

            bool originalLeaf = ((int)v[x].size() == 1);

            if(originalLeaf){
                cnt++;

                if(fre % 2 == 0){
                    leafs.push_back(x);
                }
            }
            else{
                if(fre % 2 == 1){
                    leafs.push_back(x);
                }
            }

            i = j;
        }

        int finalLeafParity = (siz[1] + k - cnt) % 2;

        if(finalLeafParity == 1){
            cout << -1 << endl;
        }
        else{
            cout << answer_virtual(leafs) + k << endl;
        }
    }

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...