DDOSvoid's Blog

CF 932D Tree

发表于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/contest/932/problem/D

Solution

注意到每次跳到第一个大于等于当前节点的点

这个东西显然可以倍增维护

需要注意的是，不管是 $sum$ 和 $max$ 我们在维护倍增数组的时候都不能算上起点

时间复杂度 $O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstdio>
#define maxn 400010
#define ll long long
using namespace std;

int m, cnt;

int f[maxn][21], nxt[maxn][21]; 

ll mx[maxn][21], a[maxn], sum[maxn][21];

int lans;
inline void solve_1() {
    ll u, w, v; cin >> u >> w; u ^= lans; w ^= lans; v = ++cnt;
    f[v][0] = u; a[v] = w; mx[v][0] = a[u];
    for (int i = 1; i <= 20; ++i) f[v][i] = f[f[v][i - 1]][i - 1];
    for (int i = 1; i <= 20; ++i) mx[v][i] = max(mx[f[v][i - 1]][i - 1], mx[v][i - 1]);
    u = v;
    for (int i = 20; ~i; --i) 
        if (f[u][i] && mx[u][i] < w) u = f[u][i];
    nxt[v][0] = f[u][0]; sum[v][0] = a[nxt[v][0]];
    for (int i = 1; i <= 20; ++i) nxt[v][i] = nxt[nxt[v][i - 1]][i - 1];
    for (int i = 1; i <= 20; ++i) sum[v][i] = sum[nxt[v][i - 1]][i - 1] + sum[v][i - 1]; 
}

inline void solve_2() {
    ll u, w; cin >> u >> w; u ^= lans; w ^= lans;
    if (w < a[u]) return (void) (cout << (lans = 0) << "\n"); lans = 1; w -= a[u]; 
    for (int i = 20; ~i; --i)
        if (nxt[u][i] && w >= sum[u][i]) w -= sum[u][i], u = nxt[u][i], lans += 1 << i;
    cout << lans << "\n"; 
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> m; cnt = 1; a[1] = 0; 
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        if (opt == 1) solve_1();
        else solve_2(); 
    } 
    return 0;
}