제출 #1234996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234996		t_holl	Spring cleaning (CEOI20_cleaning)	C++20	17 / 100	49 ms	14408 KiB

cleaning

#include <bits/stdc++.h>
#define int long long

#define MULTITEST false

using namespace std;

const int INF = 1e18;

vector<int> vp;
vector<vector<int>> roads;

int res = 0;

vector<int> cost;
vector<int> cost_prefix;
vector<int> rcost_prefix;
vector<int> parents;

int compute (int node, int parent) {
    int cnt = 0;
    for (int next : roads[node]) if (next != parent)
        cnt += compute(next, node);
    if (cnt == 0) cnt ++;

    if ((cnt & 1) == 0) cost[node] ++;
    cost[node] ++;
    if (parent == -1) cost[node] = 0;

    return cnt;
}
void dfs (int node, int parent) {
    cost_prefix[node]  = cost[node];
    rcost_prefix[node] = parent == -1 ? 0 : 3 - cost[node];
    if (parent != -1) {
         cost_prefix[node] +=  cost_prefix[parent];
        rcost_prefix[node] += rcost_prefix[parent];

        parents[node] = parent;
    }
    
    for (int next : roads[node]) if (next != parent)
        dfs(next, node);
}

void solve () {
    int N, Q; cin >> N >> Q;

    vp.resize(N);
    roads.resize(N);
    cost .resize(N);
    cost_prefix.resize(N);
    rcost_prefix.resize(N);
    parents.resize(N);

    vector<int> deg(N);

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

        roads[a].push_back(b);
        roads[b].push_back(a);
        deg[a] ++; deg[b] ++;
    }

    int root = 0;
    for (; root < N; root ++)
        if (deg[root] != 1)
            break ;
    
    compute(root, -1);
    dfs(root, -1);

    int res = 0;
    for (int u : cost)
        res += u;
    int leaf = 0;
    for (int u : deg) if (u == 1)
        leaf ++;
    
    for (int i = 0; i < Q; i ++) {
        int d;
        cin >> d;
        if (d != 1) {
            for (int j = 0; j < d; j ++) {
                int x;
                cin >> x;
            }
            continue ;
        }

        int x;
        cin >> x;
        x --;

        int nleaf = leaf;
        if (deg[x] != 1)
            nleaf ++;

        if ((nleaf & 1) == 1) {
            cout << -1 << "\n";
            continue ;
        }

        if (deg[x] == 1) {
            cout << res + 1 << "\n";
        } else {
            int tres = res + 1 + rcost_prefix[x] - cost_prefix[x];
            cout << tres << "\n";
        }
    }
}

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

    int T = 1;
    if (MULTITEST) cin >> T;

    for (int t = 0; t < T; t ++) solve();
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 17 / 17
• Subtask 7: 0 / 30