QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#480517 | #7305. Lowest Common Ancestor | _LAP_ | WA | 24ms | 14492kb | C++14 | 2.3kb | 2024-07-16 16:18:02 | 2024-07-16 16:18:03 |
Judging History
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'