QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344853#7305. Lowest Common AncestorIBoryTL 0ms0kbC++172.0kb2024-03-05 16:11:382024-03-05 16:11:38

Judging History

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

  • [2024-03-05 16:11:38]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

3
1 2 3
1 1
5
1 2 3 4 5
1 2 2 1

output:


result: