제출 #406318

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
406318		atoiz	Arboras (RMI20_arboras)	C++14	100 / 100	494 ms	19932 KiB

arboras

/*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 / 11
• Subtask 2: 13 / 13
• Subtask 3: 31 / 31
• Subtask 4: 45 / 45