QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#480517#7305. Lowest Common Ancestor_LAP_WA 24ms14492kbC++142.3kb2024-07-16 16:18:022024-07-16 16:18:03

Judging History

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

  • [2024-07-16 16:18:03]
  • 评测
  • 测评结果:WA
  • 用时:24ms
  • 内存:14492kb
  • [2024-07-16 16:18:02]
  • 提交

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() {
    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;
}

详细

Test #1:

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

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
Wrong Answer
time: 24ms
memory: 14492kb

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:

887
6372
889
20427
21897
21898
21899
7096
7179
47267
31657
57515
3405
6810
16053
24241
22833
10218
21074
25981
38747
11835
16063
10224
57242
10226
66877
7183
14366
15410
14368
5758
9451
6683
11109
6685
24891
24892
35244
29158
41333
29160
51071
43575
59109
62996
93562
93563
98560
88010
100248
99119
7...

result:

wrong answer 3rd numbers differ - expected: '11857', found: '889'