Submission #1287141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287141		thanhcodedao	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	156 ms	20196 KiB

cleaning

/****ThanhCodeDao*****/
/*******Azazel*******/
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define checkbit(mask,i) ((mask>>i)&1)
#define bit(i) (1<<i)
#define MLog 21
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
typedef long long ll;
const ll maxN = 2e5+366, modd = 1e9+7;
struct Point {
    ll x,y;
};
ll cross(Point p,Point q,Point r) { // vi tri r voi duong pq >0 la ben trai, =0 la thang hang
    ll val = (q.x-p.x)*(r.y-q.y) - (q.y-p.y)*(r.x-q.x);
    if(val < 0) return -1;
    if(val > 0) return 1;
    return 0;
}
ll dot(Point vecA,Point vecB) { // tra ve >0 la nhon, <0 la tu, =0 la vuong, 2 vecto phai chung goc
    ll val = vecA.x*vecB.x + vecA.y*vecB.y;
    if(val < 0) return -1;
    if(val > 0) return 1;
    return 0;
}
double triarea(Point p,Point q,Point r) { // cross(pq * pr) / 2
    double cross = (q.x-p.x)*(r.y-q.y) - (q.y-p.y)*(r.x-q.x);
    return fabs(cross)/2.0;
}
/* de cho

*/
/* nhan xet nho

*/
/* nhan xet tu thuat trau
*/
int n,q;
int root = -1;
int cntleaf = 0;
vector<int> adj[maxN];
vector<int> tree[maxN];
int up[maxN], dp[maxN];

void dfs(int u,int par) {
    if(adj[u].size() == 1) {
        up[u] = 1;
        dp[u] = 1;
        return;
    }
    for(int v : adj[u]) {
        if(v==par) continue;
        dfs(v,u);
        up[u] += up[v];
        dp[u] += dp[v];
    }
    up[u] %= 2;
    if(up[u] == 0) up[u] = 2;
    if(par != 0) dp[u] += up[u];
}

vector<int> vertex;
void reset() {
    for(int u : vertex) {
        adj[u].pop_back();
    }
    vertex.clear();
    cntleaf = 0;
}
void sub12() {
    while(q--) {
        int d;
        cin >> d;
        int all = n;
        for(int i = 1; i<=d; i++) {
            int u;
            cin >> u;
            ++all;
            adj[u].pb(all);
            adj[all].pb(u);
            vertex.pb(u);
            vertex.pb(all);
        }
        for(int i = 1; i<=all; i++) {
            cntleaf += (adj[i].size() == 1);
            if(adj[i].size() != 1) root = i;
        }
        if(cntleaf%2) {
            cout << -1 << '\n';
            reset();
            continue;
        }
        dfs(root,0);
        cout << dp[root] << '\n';
        for(int i = 1; i<=all; i++) {
            dp[i] = up[i] = 0;
        }
        reset();
    }
}
int is_leaf[maxN];
int exist[maxN];

int sz[maxN],depth[maxN], chainHead[maxN], chainId[maxN], cntPos = 0, cntChain = 1, a[maxN], pos[maxN];
int parent[maxN];
pair<int,int> st[maxN*4];
// F la cnt1, S la cnt2
int lz[maxN*4];
void build(int id,int l,int r) {
    if(l==r){
        st[id].F = (up[a[l]]%2 == 1); // dinh o vi tri nay trong hld
        st[id].S = (up[a[l]]%2 == 0);
        return;
    }
    int mid = (l+r)/2;
    build(2*id,l,mid);
    build(2*id+1,mid+1,r);
    st[id].F = st[id*2].F + st[id*2+1].F;
    st[id].S = st[id*2].S + st[id*2+1].S;
}
void push(int id){
    if(lz[id]){
        lz[id*2] ^= lz[id];
        lz[id*2+1] ^= lz[id];
        swap(st[id*2].F, st[id*2].S);
        swap(st[id*2+1].F, st[id*2+1].S);
        lz[id] = 0;
    }
}
void uplz(int id,int l,int r,int u,int v) {
    if(v < l || r < u || l > r) return;
    if(u<=l and r<=v){
        swap(st[id].F, st[id].S);
        lz[id] ^= 1;
        return;
    }
    int mid = (l+r)/2;
    push(id);
    uplz(2*id,l,mid,u,v);
    uplz(2*id+1,mid+1,r,u,v);
    st[id].F = st[id*2].F + st[id*2+1].F;
    st[id].S = st[id*2].S + st[id*2+1].S;
}
int get(int id,int l,int r,int u,int v){
    if(v < l || r < u || l > r) return 0;
    if(u<=l and r<=v) return st[id].F;
    push(id);
    int mid = (l+r)/2;
    return get(2*id,l,mid,u,v) + get(2*id+1,mid+1,r,u,v);
}
void pre_dfs(int u,int par){
    sz[u] = 1;
    parent[u] = par;
    for(int v : adj[u]){
        if(v==par) continue;
        pre_dfs(v,u);
        sz[u] += sz[v];
        depth[v] = depth[u] + 1;
    }
}
void hld(int u,int par){
    if(chainHead[cntChain] == 0){
        chainHead[cntChain] = u;
    }
    chainId[u] = cntChain;
    a[++cntPos] = u;
    pos[u] = cntPos;
    int bigchild = 0;
    for(int v : adj[u]){
        if(v==par) continue;
        if(sz[v] > sz[bigchild]) bigchild = v;
    }
    if(bigchild){
        hld(bigchild, u);
    }
    for(int v : adj[u]){
        if(v==par or v==bigchild) continue;
        ++cntChain;
        hld(v,u);
    }
}

void upHld(int u,int v){
    int baseu = u, basev = v;
    while(chainId[u] != chainId[v]){
//        cout << 'r' << '\n';
        if(depth[chainHead[chainId[u]]] < depth[chainHead[chainId[v]]]) swap(u,v); // u sau hon v
        uplz(1,1,n,pos[ chainHead[chainId[u] ] ], pos[u]);
        u = parent[chainHead[chainId[u]]];
    }
    if(pos[u] > pos[v]) swap(u,v);

    uplz(1,1,n,pos[u],pos[v]);
}

void sub34() {
    for(int i = 1; i<=n; i++) {
        if(adj[i].size() == 1) is_leaf[i] = 1;
        if(adj[i].size() != 1) root = i;
        cntleaf += is_leaf[i];
    }
    dfs(root,0);
    pre_dfs(root,0);
    hld(root,0);
    build(1,1,n);
//    cout << get(1,1,n,pos[3],pos[3]);
    while(q--) {
        int d;
        cin >> d;
        vector<int> vertex, realup;
        int new_cntleaf = cntleaf;
        int ans = d;
        for(int i = 1; i<=d; i++) {
            int u;
            cin >> u;
            vertex.pb(u);
            if(is_leaf[u] and exist[u] == 0) {
                exist[u] = 1;
            } else {
                ++new_cntleaf;
                realup.pb(u);
            }
        }
        if(new_cntleaf%2) {
            cout << -1 << '\n';
        } else {
            // update u len root

            for(int u : realup){
                upHld(root, u);
            }
            int cnt1 = get(1,1,n,1,n);
            int cnt2 = n - cnt1;
            int state_root = get(1,1,n,pos[root],pos[root]);
            cnt1 -= (state_root == 1);
            cnt2 -= (state_root == 0);
            ans = ans + cnt1 + cnt2*2;
            cout << ans << '\n';
            for(int u : realup){
                upHld(root,u); // dao nguoc truy van
            }
        }

        // reset
        for(int u : vertex) {
            exist[u] = 0;
        }
    }
}
void solve() {
    cin >> n >> q;
    for(int i = 1; i<=n-1; i++) {
        int u,v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
//    sub12();
    sub34();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
//    freopen("inp.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    solve();
    return 0;
}
/* simple solution */
/* simple code */

//base

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