제출 #943535

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
943535		vjudge1	Arboras (RMI20_arboras)	C++17	55 / 100	269 ms	23260 KiB

arboras

#include <bits/stdc++.h>
#define x first
#define u second
#define ll long long
#define ii pair <ll, int>

using namespace std;

const int N = 1e5 + 5;
const int mod = 1e9 + 7;

ll sumDep, sumMax, sumSec;
int n, q;
int par[N], cntDep[N], top[N];
int tin[N], tout[N], order[N], timer;
ll dep[N];
vector<int> G[N];

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];
}

ii st[N << 2];
ll lz[N << 2];

void build(int rt, int lo, int hi) {
	if (lo == hi) return st[rt] = ii(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];
}

ii getST(int l, int r, int rt, int lo, int hi) {
	if (hi < l || r < lo) return ii(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;
}

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

ii 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));
}

int high[N], mxhigh = 0;

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];
		high[v] = high[u] + 1;
		mxhigh = max(mxhigh, high[v]);
		dfs(v);
	}
	tout[u] = timer;
}

void solve(){
    cin >> n;
	for (int u = 2; u <= n; ++u) {
		cin >> par[u];
		++par[u];
		G[par[u]].push_back(u);
	}
	dep[1] = 1;
	bool ck = true;
	for (int u = 2; u <= n; ++u) {
		cin >> dep[u];
		if (dep[u] != 1e8) ck = false;
	}

	high[1] = 1;
	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) % mod << '\n';

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

		sumDep += (tout[u] - tin[u] + 1) * x;
		sumMax += (tout[u] - tin[u] + 1) * x;
		sumSec += (tout[u] - tin[u] + 1) * x;

		ii 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];
			if (curTop == 1) break;
			int p = par[curTop];
			ii ve = getMaxDep(p);
			if (ve > mx) {
				ii 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;
			}
		}
		if ((n <= 1e3 && q <= 1e3) || mxhigh <= 100 || ck) cout << (sumMax + sumSec - 2 * sumDep) % mod << '\n';
		modify(tin[u], tout[u], x, 1, 1, n);
	}
}

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

	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 31 / 31
• Subtask 4: 0 / 45