QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#344853 | #7305. Lowest Common Ancestor | IBory | TL | 0ms | 0kb | C++17 | 2.0kb | 2024-03-05 16:11:38 | 2024-03-05 16:11:38 |
answer
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAX = 200007, LIM = 500;
vector<int> G[MAX];
int W[MAX], H[MAX], P[MAX], Z[MAX], in[MAX], out[MAX], top[MAX], dn;
int S[MAX];
int DFS(int cur, int prev) {
H[cur] = H[prev] + 1;
P[cur] = prev;
int& ret = Z[cur] = 1;
for (int& next : G[cur]) {
ret += DFS(next, cur);
if (Z[next] > Z[G[cur][0]]) swap(next, G[cur][0]);
}
return ret;
}
void DFS2(int cur) {
in[cur] = ++dn;
for (int next : G[cur]) {
top[next] = (next == G[cur][0] ? top[cur] : next);
DFS2(next);
}
out[cur] = dn;
}
int LCA(int a, int b) {
while (top[a] != top[b]) {
if (H[top[a]] > H[top[b]]) swap(a, b);
b = P[top[b]];
}
return (in[a] < in[b] ? a : b);
}
struct BIT {
ll T[MAX];
void Clear(int i) {
for (; i < MAX; i += i & -i) T[i] = 0;
}
void Update(int i, ll v) {
for (; i < MAX; i += i & -i) T[i] += v;
}
ll Query(int L, int R) {
ll ret = 0; L--;
for (; R; R -= R & -R) ret += T[R];
for (; L; L -= L & -L) ret -= T[L];
return ret;
}
ll PathQuery(int p) {
ll ret = 0;
while (p) {
ret += Query(in[top[p]], in[p]);
p = P[top[p]];
}
return ret;
}
} T;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N;
while (cin >> N, !cin.eof()) {
for (int i = 1; i <= N; ++i) cin >> W[i];
for (int i = 2; i <= N; ++i) {
int p;
cin >> p;
G[p].push_back(i);
}
DFS(1, 1);
top[1] = 1;
DFS2(1);
int lastUpdate = 0;
for (int i = 1; i <= N; ++i) {
ll ans = T.PathQuery(i);
for (int j = lastUpdate + 1; j < i; ++j) ans += W[LCA(i, j)];
if (1 < i) cout << ans << '\n';
if (i % LIM == 0) {
for (int j = N; j > 0; --j) {
if (lastUpdate < j && j <= i) S[j]++;
for (int next : G[j]) S[j] += S[next];
for (int next : G[j]) T.Update(in[next], W[j] * (S[j] - S[next]));
}
memset(S, 0, (N + 1) * 4);
lastUpdate = i;
}
}
for (int i = 1; i <= N; ++i) {
G[i].clear();
T.Clear(i);
}
dn = 0;
}
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
3 1 2 3 1 1 5 1 2 3 4 5 1 2 2 1