260304 模拟赛

T1

给定一棵有根树，将一些点染色，使得每个叶子 \(i\) 到根路径上第一个被染色的点颜色为 \(a_i\)，最少化染色点的数量。

\(n\le 2\times 10^6\)

记只考虑子树 \(u\) 的答案为 \(f[u]\)。发现子树外的颜色属于某个特定集合 \(b[u]\) 的时候子树内答案会减一。然后发现 \(b[u]\) 为所有 \(b[v]\) 中的众数构成的集合。于是用 dsu 瞎做一遍即可。时间复杂度 \(O(n\log n)\)。

代码

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
const int N = 2e6 + 10;

inline void read(int &x) {
    char ch;
    while(!isdigit(ch = getchar_unlocked()));
    x = ch - '0';
    while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - '0';
}
inline void write(int x) {
    char buf[60], top = 0;
    do buf[++top] = x % 10 + '0', x /= 10; while(x);
    while(top) putchar_unlocked(buf[top--]);
    putchar_unlocked('\n');
}

struct Edge {
    int v, next;
} pool[N];
int ne, head[N];
inline void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n;
int a[N], d[N], sz[N], son[N];

int f[N];
void dfs1(int u) {
    sz[u] = 1;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        dfs1(v); sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}
vector<int> dfs2(int u, unordered_map<int, int> &mp) {
    if(!son[u]) {
        f[u] = 1; mp[a[u]] = 1;
        return vector<int>(1, a[u]);
    }
    vector<int> b[d[u] + 1];
    b[1] = dfs2(son[u], mp);
    f[u] += f[son[u]];
    int mx = 1;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == son[u]) continue;
        unordered_map<int, int> mp1;
        vector<int> tmp = dfs2(v, mp1);
        f[u] += f[v];
        for(int i : tmp) b[++mp[i]].push_back(i), mx = max(mx, mp[i]);
    }
    f[u] -= mx - 1;
    if(mx == 1) {
        return b[1];
    } else {
        mp.clear();
        for(int i : b[mx]) mp[i] = 1;
        return b[mx];
    }
}

int main() {

    freopen("pvz.in", "r", stdin);
    freopen("pvz.out", "w", stdout);

    read(n);
    for(int i = 2; i <= n; i++) {
        int x; read(x); d[x]++;
        addEdge(x, i);
    }
    for(int i = 1; i <= n; i++) read(a[i]);
    unordered_map<int, int> mp;
    dfs1(1);
    dfs2(1, mp);
    write(f[1]);

    return 0;
}

T2

给定一棵无根树，边有正整数长度。在时刻 \(0\)，你可以在树上放置任意数量的棋子。棋子可以移动，但任意时刻的速度不能超过 \(1\) 单位每秒。有 \(m\) 个限制，第 \(i\) 个限制形如要求在 \(t_i\) 时刻，\(p_i\) 点上至少需要有 \(v_i\) 个棋子。最少化初始的棋子数量。

\(n,m\le 10^5,~w\le 10^3,~t_i\le 10^8,~v_i\le 10^4\)

肯定是建出图，然后转化成最小链覆盖，然后用 Dilworth 定理转化成最长反链。

考察两个限制不能相互到达的充要条件：\(d_x+d_y-2d_{lca}>|t_x-t_y|\)，即 \(d_x+d_y-2d_{lca}>t_x-t_y\) 对任意 \(x\ne y\) 成立。移项：\(t_y+d_y>t_x-d_x+2d_{lca}\)，于是限制转化为存在一个长度为 \(2d_{lca}\) 区间 \([i,i+2d_{lca}]\) 使得所有 \(t_x+d_x\) 都在区间右边，所有 \(t_x-d_x\) 都在区间左边，其中 \(i\) 是任意实数。进一步观察到 \(i\) 只取 \(\frac{\Z}{2}\) 就行。

于是考虑设 \(f_{u,i}\) 表示 \(u\) 子树内，区间左端点为 \(i\) 时合法，最长反链的权值和。考虑转移，由于儿子到父亲时区间长度会减小，因此需要进行 \(f'_{v,i}\gets f_{v,i-j},~j\in [0,2w]\) 的转移。考虑维护差分数组，用两个 set 分别维护 +-，注意到上面扩展的时候会把所有 - 向右平移，同时合并一些 -+，用一个堆维护所有可能发生合并的 -+ 的距离，用一个 tag 维护平移。

然后发现 \(u\) 节点本身的限制不太好搞，因为它本身是不满足这个限制的（因为自己可以走到自己），于是考虑让父亲处理自己的限制。发现这样形如先进行 \(1\) 的扩展（\(f\to f'\)），然后加入 \(f_{t-d}+v\to f'_{t-d+1/2}\)。注意到原本 \(f'_{t-d+1/2}=\max(f_{t-d+1/2},~f_{t-d},~f_{t-d-1/2})\)，那么增量等于 \(\max(0,f_{t-d}+v-\max(f_{t-d+1/2},~f_{t-d},~f_{t-d-1/2}))=\max(0,v-\max(f_{t-d+1/2}-f_{t-d},~f_{t-d-1/2}-f_{t-d},0))\) 做几次单点查询和单点加即可。

于是时间复杂度 \(O(n\log^2n)\)，瓶颈在启发式合并。

代码

#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<cassert>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

struct Edge {
    int v, w, next;
} pool[2 * N];
int ne, head[N];
inline void addEdge(int u, int v, int w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
}

struct Op {
    int t, v;
    inline bool operator<(const Op &b) const {
        if(t != b.t) return t < b.t;
        return v > b.v;
    }
    inline bool operator==(const Op &b) const {
        return t == b.t;
    }
};
struct myPair {
    ll p, v;
    inline bool operator<(const myPair &b) const {
        return v > b.v;
    }
};

int n, m;
ll dep[N];
vector<Op> op[N];
map<ll, ll> mp1[N], mp2[N]; ll f[N];
priority_queue<myPair> que[N];

void update(int id, ll v) {
    if(v && !que[id].empty()) assert(que[id].top().v > f[id]);
    while(!que[id].empty() && que[id].top().v <= f[id] + v) {
        myPair u = que[id].top(); que[id].pop();
        auto tmp = mp1[id].lower_bound(u.p); if(tmp == mp1[id].end() || tmp->first != u.p) continue; ll &l = tmp->second;
        tmp = mp2[id].lower_bound(u.p + u.v); if(tmp == mp2[id].end() || tmp->first != u.p + u.v) continue; ll &r = tmp->second;
        if(-l < r) {
            r += l, l = 0, mp1[id].erase(u.p);
            auto it = mp1[id].upper_bound(u.p + u.v - f[id]);
            if(it != mp1[id].begin()) {
                --it; assert(it->first < u.p);
                que[id].push({it->first, u.p + u.v - it->first});
            }
        } else if(-l > r) {
            l += r, r = 0, mp2[id].erase(u.p + u.v);
            auto it = mp2[id].lower_bound(u.p + f[id]);
            if(it != mp2[id].end()) {
                assert(it->first > u.p + u.v);
                que[id].push({u.p, it->first - u.p});
            }
        } else {
            l = r = 0, mp1[id].erase(u.p), mp2[id].erase(u.p + u.v);
            auto it1 = mp1[id].upper_bound(u.p + u.v - f[id]);
            auto it2 = mp2[id].lower_bound(u.p + f[id]);
            if(it1 != mp1[id].begin() && it2 != mp2[id].end()) {
                --it1; assert(it1->first < u.p), assert(it2->first > u.p + u.v);
                que[id].push({it1->first, it2->first - it1->first});
            }
        }
    }
    f[id] += v;
}

void insert(int id, ll p, ll v) {
    if(v == 0) return;
    if(v > 0) {
        auto it = mp1[id].upper_bound(p - f[id]);
        if(it != mp1[id].begin()) {
            --it;
            que[id].push({it->first, p - it->first});
        }
        mp2[id][p] += v;
    } else {
        auto it = mp2[id].lower_bound(p);
        p -= f[id];
        if(it != mp2[id].end()) {
            que[id].push({p, it->first - p});
        }
        mp1[id][p] += v;
    }
    update(id, 0);
}

void merge(int x, int y) {
    if(mp1[x].size() + mp2[x].size() < mp1[y].size() + mp2[y].size()) {
        merge(y, x);
        swap(que[x], que[y]); swap(mp1[x], mp1[y]), swap(mp2[x], mp2[y]), swap(f[x], f[y]);
        return;
    }
    for(auto [pos, val] : mp1[y]) insert(x, pos + f[y], val);
    for(auto [pos, val] : mp2[y]) insert(x, pos, val);
    map<ll, ll>().swap(mp1[y]), map<ll, ll>().swap(mp2[y]), priority_queue<myPair>().swap(que[y]);
}

inline ll query(int id, ll p) {
    auto it = mp1[id].find(p - f[id]);
    if(it != mp1[id].end()) return it->second;
    it = mp2[id].find(p);
    if(it != mp2[id].end()) return it->second;
    return 0;
}

myPair buf[N]; int top;
void dfs(int u, int fa) {
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v, w = pool[e].w;
        if(v == fa) continue;
        dep[v] = dep[u] + w;
        dfs(v, u);
        for(Op &o : op[v]) {
            ll tmp = 2 * (o.t - dep[v]) + 1;
            buf[++top] = {tmp, max(0ll, o.v - max(0ll, max(-query(v, tmp - 1), query(v, tmp))))};
        }
        update(v, 2);
        while(top) insert(v, buf[top].p, buf[top].v), insert(v, buf[top].p + 1, -buf[top].v), top--;
        update(v, 4ll * w - 2);
        merge(u, v);
    }
}

int main() {

    freopen("cake.in", "r", stdin);
    freopen("cake.out", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        addEdge(u, v, w), addEdge(v, u, w);
    }
    addEdge(0, 1, 1), addEdge(1, 0, 1);
    cin >> m;
    for(int i = 1; i <= m; i++) {
        int t, p, v; cin >> t >> v >> p;
        op[p].push_back({t, v});
    }
    for(int i = 1; i <= n; i++) sort(op[i].begin(), op[i].end()), op[i].resize(unique(op[i].begin(), op[i].end()) - op[i].begin());
    dfs(0, 0);
    ll ans = 0, cur = 0;
    for(auto i = mp1[0].begin(), j = mp2[0].begin(); i != mp1[0].end() || j != mp2[0].end(); ) {
        if(i != mp1[0].end() && (j == mp2[0].end() || i->first + f[0] < j->first)) cur += i->second, i++;
        else cur += j->second, j++;
        ans = max(ans, cur);
    }
    cout << ans << '\n';

    return 0;
}