oj.uz

Submission #406318

# Submission time Handle Problem Language Result Execution time Memory
406318 2021-05-17T11:20:29 Z atoiz Arboras (RMI20_arboras) C++14
100 / 100
 494 ms 19932 KB 
/*input
5
0 0 1 1
0 0 0 0
10
1 2
2 2
3 2
4 2
4 1
3 1
2 1
1 1
4 1000
2 1000
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;
using ver_t = pair<ll, int>;
#define x first
#define u second

const int MAXN = 101001;
ll sumDep, sumMax, sumSec;
int N, Q, par[MAXN], cntDep[MAXN], top[MAXN], tin[MAXN], tout[MAXN], order[MAXN], timer;
ll dep[MAXN];
vector<int> G[MAXN];
ver_t st[MAXN << 2];
ll lz[MAXN << 2];

int getSurroundChild(int u, int v) {
	int lo = 0, hi = int(G[u].size()) - 1;
	while (lo < hi) {
		int md = (lo + hi + 1) >> 1;
		if (tin[v] < tin[G[u][md]]) hi = md - 1;
		else lo = md;
	}
	return G[u][lo];
}

void build(int rt, int lo, int hi) {
	if (lo == hi) return st[rt] = ver_t(dep[order[lo]], order[lo]), lz[rt] = 0, void(0);
	int md = (lo + hi) >> 1, lc = rt << 1, rc = lc | 1;
	build(lc, lo, md), build(rc, md + 1, hi);
	st[rt] = max(st[lc], st[rc]), lz[rt] = 0;
}

void modify(int l, int r, ll x, int rt, int lo, int hi) {
	if (hi < l || r < lo) return; 
	if (l <= lo && hi <= r) return st[rt].x += x, lz[rt] += x, void(0);
	int md = (lo + hi) >> 1, lc = rt << 1, rc = lc | 1;
	modify(l, r, x, lc, lo, md);
	modify(l, r, x, rc, md + 1, hi);
	st[rt] = max(st[lc], st[rc]), st[rt].x += lz[rt];
}

ver_t getST(int l, int r, int rt, int lo, int hi) {
	if (hi < l || r < lo) return ver_t(0, 0); 
	if (l <= lo && hi <= r) return st[rt];
	int md = (lo + hi) >> 1, lc = rt << 1, rc = lc | 1;
	auto ver = max(getST(l, r, lc, lo, md), getST(l, r, rc, md + 1, hi));
	ver.x += lz[rt];
	return ver;
}

ver_t getMaxDep(int u) {
	return getST(tin[u], tout[u], 1, 1, N);
}

ver_t getSecDep(int u) {
	int mx = getMaxDep(u).u;
	if ((int) G[u].size() <= 1) return getST(tin[u], tin[u], 1, 1, N);
	int v = getSurroundChild(u, mx);
	return max(getST(tin[u], tin[v] - 1, 1, 1, N), getST(tout[v] + 1, tout[u], 1, 1, N));
}

void dfs(int u) {
	tin[u] = ++timer;
	order[tin[u]] = u;
	for (int v : G[u]) {
		cntDep[v] = cntDep[u] + 1;
		dep[v] += dep[u];
		dfs(v);
	}
	tout[u] = timer;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int u = 2; u <= N; ++u) {
		cin >> par[u];
		++par[u];
		G[par[u]].push_back(u);
	}
	dep[1] = 1;
	for (int u = 2; u <= N; ++u) {
		cin >> dep[u];
	}

	dfs(1);
	build(1, 1, N);

	sumDep = 0, sumMax = 0, sumSec = 0;
	for (int u = 1; u <= N; ++u) top[u] = u;
	for (int u = 1; u <= N; ++u) {
		sumDep += dep[u];
		sumMax += dep[getMaxDep(u).u];
		sumSec += dep[getSecDep(u).u];

		int mx = getMaxDep(u).u;
		if (cntDep[top[mx]] > cntDep[u]) top[mx] = u;
	}
	cout << (sumMax + sumSec - 2 * sumDep) % 1000000007 << '\n';

	cin >> Q;
	while (Q--) {
		int u; ll x;
		cin >> u >> x;
		++u;

		sumDep += (tout[u] - tin[u] + 1) * x; // in subtree rooted at u
		sumMax += (tout[u] - tin[u] + 1) * x; // in subtree rooted at u
		sumSec += (tout[u] - tin[u] + 1) * x; // in subtree rooted at u

		ver_t mx = getST(tin[u], tout[u], 1, 1, N);
		mx.x += x;
		sumMax += (cntDep[u] - cntDep[top[mx.u]]) * x;

		while (true) {
			int curTop = top[mx.u];
			// cout << mx.u << ": " << curTop << endl;
			if (curTop == 1) break;
			// cout << u << ' ' << x << ": " << curTop << endl;
			int p = par[curTop];
			ver_t ve = getMaxDep(p);
			if (ve > mx) {
				ver_t tmp = getSecDep(p);
				if (tmp < mx) sumSec += mx.x - tmp.x;
				break;
			} else {
				sumSec += ve.x - getSecDep(p).x;

				int newTop = top[ve.u];
				sumMax += (cntDep[curTop] - cntDep[newTop]) * (mx.x - ve.x);
				top[ve.u] = getSurroundChild(p, ve.u);
				top[mx.u] = newTop;
			}
		}

		// for (int u = 1; u <= N; ++u) cout << top[u] << ' '; cout << endl;
		cout << (sumMax + sumSec - 2 * sumDep) % 1000000007 << '\n';
		modify(tin[u], tout[u], x, 1, 1, N);
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2764 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2764 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 16572 KB Output is correct
2 Correct 304 ms 15124 KB Output is correct
3 Correct 349 ms 15296 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 18220 KB Output is correct
2 Correct 254 ms 19492 KB Output is correct
3 Correct 435 ms 16416 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2764 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2764 KB Output is correct
4 Correct 494 ms 16572 KB Output is correct
5 Correct 304 ms 15124 KB Output is correct
6 Correct 349 ms 15296 KB Output is correct
7 Correct 403 ms 18220 KB Output is correct
8 Correct 254 ms 19492 KB Output is correct
9 Correct 435 ms 16416 KB Output is correct
10 Correct 402 ms 17920 KB Output is correct
11 Correct 240 ms 19240 KB Output is correct
12 Correct 383 ms 16260 KB Output is correct
13 Correct 294 ms 19432 KB Output is correct
14 Correct 224 ms 19932 KB Output is correct