2019-2020 ACM-ICPC Brazil Subregional Programming Contest D Denouncing Mafia

Denouncing Mafia

贪心 + 线段树 + \(dfs\) 序

考虑贪心地每次拿能染色最多的点，每拿走一个点，都会影响其他点的值，如果一个点被染色，则他子树的所有点的贡献值都会 - 1，因此考虑用线段树 + \(dfs\) 序的方式，对树上进行区间修改，每次询问所有点的最大贡献值即可

拿到最大贡献值后，通过那个点网上遍历到根，访问过程中，未被染色的点都要进行一次子树 - 1 的操作

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
#define pii pair<ll, ll>
vector<int>fa, L, R, rnk;
vector<ll>num;
vector<vector<int> >gra;
int tp = 0;

struct node
{
    ll val, lazy;
    int l, r, last;
};
vector<node>tr;

void dfs(int now, int d)
{
    L[now] = ++tp;
    rnk[tp] = now;
    num[tp] = d;
    for(int nex : gra[now])
    {
        if(nex == fa[now]) continue;
        dfs(nex, d + 1);
    }
    R[now] = tp;
}

inline void push_up(int now)
{
    int lson = now << 1, rson = now << 1 | 1;
    int nex = rson;
    if(tr[lson].val > tr[rson].val)
        nex = lson;
    tr[now].val = tr[nex].val;
    tr[now].last = tr[nex].last;
}

void build(int now, int l, int r)
{
    tr[now].val = tr[now].lazy = 0;
    tr[now].l = l;
    tr[now].r = r;
    if(l == r)
    {
        tr[now].val = num[l];
        tr[now].last = l;
        return;
    }
    int mid = l + r >> 1;
    build(now << 1, l, mid);
    build(now << 1 | 1, mid + 1, r);
    push_up(now);
}

void push_down(int now)
{
    if(tr[now].lazy)
    {
        int lson = now << 1, rson = now << 1 | 1;
        tr[lson].lazy += tr[now].lazy;
        tr[rson].lazy += tr[now].lazy;
        tr[lson].val += tr[now].lazy;
        tr[rson].val += tr[now].lazy;
        tr[now].lazy = 0;
    }
}

void update(int now, int L, int R, ll val)
{
    if(L <= tr[now].l && tr[now].r <= R)
    {
        tr[now].lazy += val;
        tr[now].val += val;
        return;
    }
    int mid = tr[now].l + tr[now].r >> 1;
    push_down(now);
    if(L <= mid)
        update(now << 1, L, R, val);
    if(R > mid)
        update(now << 1 | 1, L, R, val);
    push_up(now);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    fa.resize(n + 1);
    L.resize(n + 1);
    R.resize(n + 1);
    rnk.resize(n + 1);
    gra.resize(n + 1);
    tr.resize((n + 1) * 4);
    num.resize(n + 1);
    for(int i=2; i<=n; i++)
    {
        cin >> fa[i];
        gra[fa[i]].push_back(i);
    }
    dfs(1, 1);
    ll ans = 0;
    build(1, 1, n);
    vector<int>vis(n + 1);
    for(int i=0; i<k; i++)
    {
        ll x = tr[1].val, y = tr[1].last;
        if(x == 0) break;
        ans += x;
        y = rnk[y];
        while(y && vis[y] == 0)
        {
            update(1, L[y], R[y], -1);
            vis[y] = 1;
            y = fa[y];
        }
    }
    cout << ans << endl;
    return 0;
}