QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#480511#7305. Lowest Common Ancestor_LAP_WA 0ms15176kbC++142.3kb2024-07-16 16:16:482024-07-16 16:16:48

Judging History

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

  • [2024-07-16 16:16:48]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:15176kb
  • [2024-07-16 16:16:48]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10, M = 4e5 + 10;
int n, w[N], h[N], e[M], ne[M], idx;
inline void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }


int fa[N], dfn[N], siz[N], son[N], top[N], dfs_clock;
void dfs(int u, int f) {
    fa[u] = f, siz[u] = 1, son[u] = 0;
    for(int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i]; if(v == f) continue;
        dfs(v, u), siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}
void hld(int u, int topf) {
    top[u] = topf, dfn[u] = ++dfs_clock;
    if(!son[u]) return;
    hld(son[u], topf);
    for(int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i]; if(v == fa[u] || v == son[u]) continue;
        hld(v, v);
    }
}
struct Fenwick {
    long long C[N];
    Fenwick() {memset(C, 0, sizeof C); }
    inline void clear() {memset(C + 1, 0, sizeof(long long) * n); }
    inline void add(int p, int x) {for(; p <= n; p += p & -p) C[p] += x; }
    inline long long ask(int l, int r) {return ask(r) - ask(l - 1); }
    inline long long ask(int p) {int r = 0; for(; p; p -= p & -p) r += C[p]; return r; }
    inline long long ask_subtree(int u) {return ask(dfn[u], dfn[u] + siz[u] - 1); }
} BIT, BIT2;

int f[N];

inline void solve() {
    cin >> n, idx = 0, dfs_clock = 0;
    memset(h + 1, -1, sizeof(int) * n);
    for(int i = 1; i <= n; i ++)
        cin >> w[i];
    for(int i = 2; i <= n; i ++) {
        int x; cin >> x;
        add(x, i), add(i, x);
    }
    dfs(1, 0), hld(1, 1);
    for(int i = 1; i <= n; i ++) f[i] = 0;
    for(int i = 1; i <= n; i ++) {
        int u = i;
        f[i] += BIT.ask_subtree(u), u = top[u];
        while(fa[u]) {
            f[i] += w[fa[u]] * (BIT.ask_subtree(fa[u]) - BIT.ask_subtree(u));
            u = top[fa[u]];
        }
        int lst = i;
        while(lst) {
            int now = top[lst];
            if(now != lst) f[i] += BIT2.ask(dfn[now], dfn[lst] - 1);
            lst = fa[now];
        }
        u = i;
        BIT.add(dfn[u], 1);
        while(u) {
            BIT2.add(dfn[u], w[u]);
            u = fa[top[u]];
        }
    }
    for(int i = 2; i <= n; i ++)
        cout << f[i] << '\n';
    BIT.clear(), BIT2.clear();
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    while(cin >> n) solve();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 15176kb

input:

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

output:

5
10
15

result:

wrong answer 1st numbers differ - expected: '1', found: '5'