QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#480511 | #7305. Lowest Common Ancestor | _LAP_ | WA | 0ms | 15176kb | C++14 | 2.3kb | 2024-07-16 16:16:48 | 2024-07-16 16:16:48 |
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() {
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'