QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#351049#7305. Lowest Common AncestorIBoryWA 100ms22992kbC++172.9kb2024-03-11 13:36:402024-03-11 13:36:40

Judging History

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

  • [2024-03-11 13:36:40]
  • 评测
  • 测评结果:WA
  • 用时:100ms
  • 内存:22992kb
  • [2024-03-11 13:36:40]
  • 提交

answer

#include <bits/stdc++.h>
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int SZ = 1 << 18;
vector<int> G[SZ];
int W[SZ], H[SZ], P[SZ], Z[SZ], in[SZ], out[SZ], top[SZ], dn;
ll U[SZ << 1];

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 Seg {
	ll T[SZ << 1], Z[SZ << 1];
	void Push(int n) {
		if (!Z[n]) return;
		if (n < SZ) {
			Z[n * 2] += Z[n];
			Z[n * 2 + 1] += Z[n];
		}
		// cout << "temp " << U[n] << '\n';
		T[n] += Z[n] * U[n];
		Z[n] = 0;
	}
	void Update(int L, int R, int v, int sL = 1, int sR = SZ, int n = 1) {
		Push(n);
		if (R < sL || sR < L) return;
		if (L <= sL && sR <= R) {
			Z[n] += v;
			Push(n);
			return;
		}
		int mid = (sL + sR) >> 1;
		Update(L, R, v, sL, mid, n * 2);
		Update(L, R, v, mid + 1, sR, n * 2 + 1);
		T[n] = T[n * 2] + T[n * 2 + 1];
	}
	ll Query(int L, int R, int sL = 1, int sR = SZ, int n = 1) {
		Push(n);
		if (R < sL || sR < L) return 0;
		if (L <= sL && sR <= R) return T[n];
		int mid = (sL + sR) >> 1;
		return Query(L, R, sL, mid, n * 2) + Query(L, R, mid + 1, sR, n * 2 + 1);
	}
	void PathUpdate(int a, int b) {
		while (top[a] != top[b]) {
			if (H[top[a]] > H[top[b]]) swap(a, b);
			Update(in[top[b]], in[b], 1);
			b = P[top[b]];
		}
		if (H[a] > H[b]) swap(a, b);
		Update(in[a], in[b], 1);
	}
	ll PathQuery(int a, int b) {
		ll ret = 0;
		while (top[a] != top[b]) {
			if (H[top[a]] > H[top[b]]) swap(a, b);
			ret += Query(in[top[b]], in[b]);
			b = P[top[b]];
		}
		if (H[a] > H[b]) swap(a, b);
		ret += Query(in[a], in[b]);
		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, 0);
		top[1] = 1;
		DFS2(1);

		for (int i = 1; i <= N; ++i) {
			int p = in[i] + SZ - 1;
			U[p] = W[i] - W[P[i]];
			while (p >>= 1) U[p] = U[p * 2] + U[p * 2 + 1];
		}

		T.PathUpdate(1, 1);
		for (int i = 2; i <= N; ++i) {
			ll ans = T.PathQuery(1, i);
			cout << ans << '\n';
			T.PathUpdate(1, i);
		}

		for (int i = 1; i <= N; ++i) {
			G[i].clear();
			ll t = (U[in[i] + SZ - 1] ? -T.Query(in[i], in[i]) / U[in[i] + SZ - 1] : 0LL);
			T.Update(in[i], in[i], t);
			int p = (i + SZ - 1) * 2;
			while (p >>= 1) U[p] = 0;
		}
		dn = 0;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 100ms
memory: 22992kb

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
11857
20427
21897
22192
26895
7096
7179
47267
48895
57515
3405
50344
54792
62980
22833
50757
69625
73230
77486
97381
67307
111284
95981
101097
105616
49965
89537
19348
71235
42122
49357
9485
13454
24274
-4657
34369
6733
12243
11989
8211
21523
29021
61911
40544
93562
98559
108242
90812
12002...

result:

wrong answer 14th numbers differ - expected: '6810', found: '50344'