Submission #1282897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282897		goldencheems	Spring cleaning (CEOI20_cleaning)	C++20	0 / 100	124 ms	26008 KiB

cleaning

/*DEP TRAI CO J SAI*/
/* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@%%##***************************+++++++++++++++++++++++++++++++++++++++++++++++***************************######%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*
   Template theo yêu cầu: bits, pragma, macros fi/se/pu, typedef ll, hàm tinh(), fast IO.
   Code: HLD + segment tree để tính sum_e min(leaves_sub_e, L - leaves_sub_e)
*/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#define fi first
#define se second
#define pu push_back
typedef long long ll;
const int MAXN = 200000 + 5; // safe bound

int n, Q;
vector<int> adj[MAXN];
int deg[MAXN];
int parentArr[MAXN], depthArr[MAXN], sz[MAXN];
int heavy[MAXN], head[MAXN], pos[MAXN], curPos;
int origLeaf[MAXN];
int subLeaf[MAXN];
int baseVal[MAXN]; // baseVal at pos[u] = subtree leaves of u
ll baseSum = 0;

void dfs1(int u,int p){
    parentArr[u]=p;
    sz[u]=1;
    heavy[u]=0;
    subLeaf[u]= (deg[u]==1 ? 1 : 0);
    for(int v: adj[u]){
        if(v==p) continue;
        depthArr[v]=depthArr[u]+1;
        dfs1(v,u);
        sz[u]+=sz[v];
        subLeaf[u]+=subLeaf[v];
        if(!heavy[u] || sz[v]>sz[heavy[u]]) heavy[u]=v;
    }
}
void dfs_hld(int u,int h){
    head[u]=h;
    pos[u]=++curPos;
    baseVal[curPos]=subLeaf[u];
    if(heavy[u]) dfs_hld(heavy[u],h);
    for(int v: adj[u]){
        if(v==parentArr[u] || v==heavy[u]) continue;
        dfs_hld(v,v);
    }
}

// segment tree for values t_i = baseVal + adds
struct Seg{
    struct Node{
        ll mn, mx, sum;
        int len;
        ll lazy;
    };
    vector<Node> st;
    int n;
    Seg(int _n=0){init(_n);}
    void init(int _n){
        n=_n;
        st.assign(4*n+5, {0,0,0,0,0});
    }
    void build(int id,int l,int r){
        st[id].lazy=0;
        st[id].len = r-l+1;
        if(l==r){
            ll v = baseVal[l];
            st[id].mn = st[id].mx = st[id].sum = v;
            return;
        }
        int m=(l+r)/2;
        build(id<<1,l,m);
        build(id<<1|1,m+1,r);
        st[id].mn = min(st[id<<1].mn, st[id<<1|1].mn);
        st[id].mx = max(st[id<<1].mx, st[id<<1|1].mx);
        st[id].sum = st[id<<1].sum + st[id<<1|1].sum;
    }
    void apply(int id, ll val){
        st[id].mn += val;
        st[id].mx += val;
        st[id].sum += val * st[id].len;
        st[id].lazy += val;
    }
    void push(int id){
        if(st[id].lazy!=0){
            apply(id<<1, st[id].lazy);
            apply(id<<1|1, st[id].lazy);
            st[id].lazy=0;
        }
    }
    void pull(int id){
        st[id].mn = min(st[id<<1].mn, st[id<<1|1].mn);
        st[id].mx = max(st[id<<1].mx, st[id<<1|1].mx);
        st[id].sum = st[id<<1].sum + st[id<<1|1].sum;
    }
    void update(int id,int l,int r,int L,int R,ll val){
        if(L>r || R<l) return;
        if(L<=l && r<=R){
            apply(id,val);
            return;
        }
        push(id);
        int m=(l+r)/2;
        update(id<<1,l,m,L,R,val);
        update(id<<1|1,m+1,r,L,R,val);
        pull(id);
    }
    // query number of positions with value > T and sum of those values
    pair<int,ll> queryGreater(int id,int l,int r,ll T){
        if(st[id].mx <= T) return {0,0};
        if(st[id].mn > T) return {st[id].len, st[id].sum};
        push(id);
        int m=(l+r)/2;
        auto L = queryGreater(id<<1,l,m,T);
        auto R = queryGreater(id<<1|1,m+1,r,T);
        return {L.first + R.first, L.second + R.second};
    }
    ll totalSum(){ return st[1].sum; }
};

Seg seg;

void path_update(int u,int v,ll val){ // here v is root (1). we'll always call path root(=1) -> u
    while(head[u] != head[v]){
        seg.update(1,1,n,pos[head[u]],pos[u], val);
        u = parentArr[head[u]];
    }
    if(pos[v] <= pos[u]) seg.update(1,1,n,pos[v],pos[u], val);
    else seg.update(1,1,n,pos[u],pos[v], val);
}

void tinh(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>Q;
    for(int i=1;i<=n;i++){ adj[i].clear(); deg[i]=0; }
    for(int i=1;i<=n-1;i++){
        int u,v; cin>>u>>v;
        adj[u].pu(v); adj[v].pu(u);
        deg[u]++; deg[v]++;
    }
    // pick root as any non-leaf (or 1 if ok)
    int root = 1;
    for(int i=1;i<=n;i++) if(deg[i]>1){ root=i; break; }
    if(root==0) root=1;
    depthArr[root]=0;
    dfs1(root,0);
    curPos=0;
    dfs_hld(root,root);
    // build segtree on positions 1..n
    seg.init(n);
    // baseVal already filled at pos
    // baseSum = sum_{edges} orig_subtree_leaves; note pos[root] corresponds to root node; its baseVal = subLeaf[root] (which equals total leaves) but we should exclude it in sums because it's not an edge.
    baseSum = 0;
    for(int i=1;i<=n;i++){
        // baseVal[pos[i]] already set
    }
    // We will keep pos[root] as well; but it's safe since edges count = n (including root position), root position value = total leaves; However we must exclude it from final sum and from counts.
    // So easiest: set baseVal[pos[root]] = 0 to exclude root's contribution.
    baseVal[pos[root]] = 0;
    // compute baseSum as sum baseVal
    baseSum = 0;
    for(int i=1;i<=n;i++) baseSum += baseVal[i];
    seg.build(1,1,n);

    // store original leaf flag
    for(int i=1;i<=n;i++) origLeaf[i] = (deg[i]==1 ? 1 : 0);
    int origLeavesTotal = 0;
    for(int i=1;i<=n;i++) origLeavesTotal += origLeaf[i];

    // process Q queries
    // Note: total number of attachments across all queries <= 1e5 per constraints
    while(Q--){
        int D; cin>>D;
        vector<int> a(D);
        for(int i=0;i<D;i++) cin>>a[i];
        if(D==0){
            // no additions: answer depends only on origLeavesTotal parity and original base
            if((origLeavesTotal % 2)==1){
                cout<<-1<<"\n";
            } else {
                // L = origLeavesTotal
                ll L = origLeavesTotal;
                ll T = L/2;
                // query number > T and sum
                auto pr = seg.queryGreater(1,1,n,T);
                ll b = pr.first;
                ll sum_big = pr.second;
                // S = current sum of t_i = baseSum (no adds)
                ll S = baseSum;
                ll ans = S + b * L - 2 * sum_big;
                cout<<ans<<"\n";
            }
            continue;
        }
        // build count map per node for attachments in this query
        unordered_map<int,int> cnt; cnt.reserve(D*2);
        for(int x: a) cnt[x]++;
        // compute lost = number of distinct aj that were original leaf
        int lost=0;
        for(auto &kv: cnt){
            int node = kv.first;
            if(origLeaf[node]) lost++;
        }
        ll L = (ll)origLeavesTotal + (ll)D - (ll)lost;
        if(L % 2 == 1){
            cout<<-1<<"\n";
            continue;
        }
        // prepare net_add per distinct node = cnt[node] - (origLeaf[node]?1:0)
        // apply updates: for each node v, add net_add[v] on path root->v
        vector<pair<int,int>> changed; changed.reserve(cnt.size());
        ll addDepthSum = 0; // sum net_add[v] * depth[v]
        for(auto &kv: cnt){
            int v = kv.first;
            int c = kv.second;
            int net = c - (origLeaf[v] ? 1 : 0);
            if(net==0) continue;
            // update path root->v by +net
            path_update(v, root, net);
            changed.emplace_back(v, net);
            addDepthSum += (ll)net * (ll)depthArr[v];
        }
        // Now compute S, b, sum_big
        ll S = baseSum + addDepthSum;
        ll T = L/2;
        auto pr = seg.queryGreater(1,1,n,T);
        ll b = pr.first;
        ll sum_big = pr.second;
        ll ans = S + b * L - 2 * sum_big;
        cout<<ans<<"\n";
        // revert updates
        for(auto &kv: changed){
            int v = kv.first; int net = kv.second;
            path_update(v, root, -net);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    tinh();
    return 0;
}

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