QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#220286#7305. Lowest Common Ancestornice_try_fuckerRE 0ms22764kbC++203.6kb2023-10-20 02:58:052023-10-20 02:58:06

Judging History

你现在查看的是最新测评结果

  • [2023-10-20 02:58:06]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:22764kb
  • [2023-10-20 02:58:05]
  • 提交

answer

// Created with gribonator.py
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#pragma GCC target("avx,tune=native")
#pragma GCC comment(linker, "/stack:200000000")

using namespace __gnu_pbds;

using namespace std;
mt19937 rng(chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count());

const int INF = 1e9 + 7, MD = 998244353, MAX = 200007, MOD = 1e9 + 7, MOD2 = MOD * MOD, LG = 17, B = 40;
const long long INFLL = 1e18 + 7;

int n, W[MAX];

vector <int> g[MAX];
int sub[MAX], up[LG][MAX], tin[MAX], tout[MAX], head[MAX], tt;

void dfs_pre(int v, int p = -1) {
    sub[v] = 1;
    for (auto& u : g[v]) if (u != p) {
        dfs_pre(u, v);
        W[u] -= W[v];
        sub[v] += sub[u];
    }
}

void dfs_hld(int v, int h, int p = -1) {
    tin[v] = tt++, up[0][v] = p, head[v] = h;
    if ((int)(g[v].size()) > 1) {
        if (g[v][0] == p) swap(g[v][0], g[v].back());
        for (int i = 1; i < (int)(g[v].size()); ++i) if (g[v][i] != p) {
            if (sub[g[v][i]] > sub[g[v][0]]) swap(g[v][0], g[v][i]);
        }
        dfs_hld(g[v][0], h, v);
        for (int i = 1; i < (int)(g[v].size()); ++i) if (g[v][i] != p) {
            dfs_hld(g[v][i], g[v][i], v);
        }
    }
}

struct node {
    long long s;
    int w, d;
    node() : s(0), w(0), d(0) {}
} t[1 << 19];

int R;

void push(int v) {
    if (!t[v].d) return;
    t[2 * v].s += t[2 * v].w * 1LL * t[v].d, t[2 * v].d += t[v].d;
    t[2 * v + 1].s += t[2 * v + 1].w * 1LL * t[v].d, t[2 * v + 1].d += t[v].d;
    t[v].d = 0;
}

void upd(int ql, int qr, int v, int nl, int nr) {
    if (ql == nl && qr == nr) {
        t[v].d++, t[v].s += t[v].w;
        return;
    }
    push(v);
    int nm = (nl + nr) / 2;
    if (qr <= nm) upd(ql, qr, 2 * v, nl, nm);
    else if (ql >= nm) upd(ql, qr, 2 * v + 1, nm, nr);
    else
        upd(ql, nm, 2 * v, nl, nm), upd(nm, qr, 2 * v + 1, nm, nr);
    t[v].s = t[2 * v].s + t[2 * v + 1].s;
}

void upd(int l, int r) { upd(l, r, 1, 0, R); }

long long get(int ql, int qr, int v, int nl, int nr) {
    if (ql == nl && qr == nr) {
        push(v);
        return t[v].s;
    }
    push(v);
    int nm = (nl + nr) / 2;
    if (qr <= nm) return get(ql, qr, 2 * v, nl, nm);
    if (ql >= nm) return get(ql, qr, 2 * v + 1, nm, nr);
    return get(ql, nm, 2 * v, nl, nm) + get(nm, qr, 2 * v + 1, nm, nr);
}

long long get(int l, int r) { return get(l, r, 1, 0, R); }

void resize(int n) {
    R = 1;
    while (R < n) R <<= 1;
    fill(t + 1, t + 2 * R, node());
}

long long hld_get(int v) {
    long long s = 0;
    while (v != -1) {
        s += get(tin[head[v]], tin[v] + 1);
        v = up[0][head[v]];
    }
    return s;
}

void hld_upd(int v) {
    while (v != -1) {
        upd(tin[head[v]], tin[v] + 1);
        v = up[0][head[v]];
    }
}

void solve() {
    tt = 0;
    for (int i = 0; i < n; ++i) g[i].clear();
    resize(n);
    for (int i = 0; i < n; ++i) cin >> W[i];
    for (int i = 1; i < n; ++i) {
        int p; cin >> p, --p;
        g[p].push_back(i), g[i].push_back(p);
    }
    dfs_pre(0);
    dfs_hld(0, 0);
    for (int i = 0; i < n; ++i) t[R + tin[i]].w = W[i];
    for (int i = R - 1; i >= 1; --i) t[i].w = t[2 * i].w + t[2 * i + 1].w;
    hld_upd(0);
    for (int i = 1; i < n; ++i) {
        cout << hld_get(i) << '\n';
        hld_upd(i);
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    while (cin >> n) solve();
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 22764kb

input:

3
1 2 3
1 1
5
1 2 3 4 5
1 2 2 1

output:

1
2
1
3
5
4

result:

ok 6 numbers

Test #2:

score: -100
Runtime Error

input:

13
887 4555 8570 5485 8611 9500 295 2499 83 4959 9772 8620 3825
4 4 1 3 7 12 2 1 9 5 8 12
16
3405 9213 9243 8188 2733 1333 1614 4907 4256 7506 4228 1286 6121 6155 4082 8084
1 12 9 4 2 13 3 8 9 7 11 15 8 1 10
5
7183 1481 9468 8242 1044
1 5 5 1
3
5758 3693 1694
1 2
20
6683 4426 5616 8166 810 4265 3000...

output:


result: