提出 #68169928

---

ソースコード 拡げる

// #define WANT_LDEBUG
#ifdef LOCAL
#include "D:/C++/include/all.h"
#else
#include <bits/stdc++.h>
#define ldebug(...)
#define cpp_version_ __cplusplus
#define REP(i, a, b) for (int i = a; i < (b); ++i)
#define RREP(i, a, b) for (int i = a; i > (b); --i)
#define FOR(i, a, b) for (int i = a; i <= (b); ++i)
#define RFOR(i, a, b) for (int i = a; i >= (b); --i)
#define REPK(i, a, b, k) for (int i = a; i < (b); i += k)
#define RREPK(i, a, b, k) for (int i = a; i > (b); i -= k)
#define FORK(i, a, b, k) for (int i = a; i <= (b); i += k)
#define RFORK(i, a, b, k) for (int i = a; i >= (b); i -= k)
using namespace std;
using bool_t = signed char;
using u32 = unsigned int;
using i64 = long long;
using i128 = __int128;
using u64 = unsigned long long;
using f64 = double;
#define fast_io()                                                              \
    std::ios::sync_with_stdio(false);                                          \
    std::cin.tie(nullptr)
template <typename T, typename U> bool ckmax(T &a, U b) {
    return a < b && (a = b, true);
}
template <typename T, typename U> bool ckmin(T &a, U b) {
    return b < a && (a = b, true);
}
#endif


constexpr int MAXN = 5e5 + 5, LOG_N = 20;
bool hs[MAXN]; //< heavy son
int Q;
array<int, LOG_N> son[MAXN];
i64 len[MAXN], lost[MAXN][LOG_N][2], x[MAXN];
array<int, 2> ch[MAXN];

void solve() {
    len[0] = len[1] = 1;
    cin >> Q;
    son[0].fill(-1);
    son[1].fill(-1);
    FOR(i, 1, Q) {
        int u = i + 1;
        cin >> ch[u][0] >> ch[u][1] >> x[i];
        len[u] = min(len[ch[u][0]] + len[ch[u][1]], static_cast<i64>(1e18));
        hs[u] = (len[ch[u][1]] > len[ch[u][0]]);
        son[u][0] = ch[u][hs[u]];
        ldebug("son[{}] = {}, len = {}\n", u, ch[u][hs[u]], len[u]);
        lost[u][0][!hs[u]] = len[ch[u][!hs[u]]];
        // ldebug("lost[{}][0][{}] = {}\n", u, !hs[u], lost[u][0][!hs[u]]);
        REP(j, 1, LOG_N) {
            if (son[u][j - 1] == -1) {
                son[u][j] = -1;
                continue;
            }
            son[u][j] = son[son[u][j - 1]][j - 1];
            REP(k, 0, 2) {
                lost[u][j][k] = lost[u][j - 1][k] + lost[son[u][j - 1]][j - 1][k];
                ldebug("lost[{}][{}][{}] = {} + {}\n", u, j, k, lost[u][j - 1][k], lost[son[u][j - 1]][j - 1][k]);
            }
        }
        array<i64, 2> seq{{1LL, len[u]}}, ns;
        while (u > 1) {
            ldebug("u = {}\n", u);
            RFOR(j, LOG_N - 1, 0) {
                if (son[u][j] == -1) continue;
                ns[0] = seq[0] + lost[u][j][0];
                ns[1] = seq[1] - lost[u][j][1];
                ldebug("u = {}, j = {}, ns = [{}, {}]\n", u, j, ns[0], ns[1]);
                if (ns[0] <= x[i] && x[i] <= ns[1]) {
                    ldebug("accept ns, now u = {}\n", son[u][j]);
                    seq = ns;
                    u = son[u][j];
                }
            }
            if (u > 1) {
                // 一定要跳一个轻儿子
                if (hs[u]) {
                    seq[hs[u]] -= len[ch[u][hs[u]]];
                } else {
                    seq[hs[u]] += len[ch[u][hs[u]]];
                }
                u = ch[u][!hs[u]];
                ldebug("jump light son, seq = [{}, {}], u = {}\n", seq[0], seq[1], u);
            }
        }
        cout << u << '\n';
    }
}
int main() {
    fast_io();
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
#ifdef DEBUG
        cerr << endl;
#endif
    }
    return 0;
}

提出情報

ジャッジ結果