Submission #943797

#	Time	Username	Problem	Language	Result	Execution time	Memory
943797		vjudge1	Arboras (RMI20_arboras)	C++17	100 / 100	800 ms	57712 KiB

arboras

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 1e5, LOG = 16, MOD = 1e9+7;

struct node{
	int sz, f, g;
};

struct tag{
	pii f, g;
	tag(){
		f = g = mp(1, 0);
	}
	tag(pii y, pii z){
		f = y, g = z;
	}
};

int n, q, p[NM+5], d[NM+5], dep[NM+5], sumd[NM+5], sz[NM+5], f[NM+5], g[NM+5], jump[NM+5][LOG+5], cur = 0;
vector <int> son[NM+5];
int head[NM+5], timer = 0, tin[NM+5], tour[NM+5], tout[NM+5];
node st[4*NM+5];
tag lazy[4*NM+5];

void dfs_sz(int u){
	dep[u] = (u == 1 ? 0 : dep[p[u]]+1);
	sumd[u] = sumd[p[u]]+d[u];
	sz[u] = 1;
	f[u] = g[u] = 0;
	for (int v : son[u]){
		dfs_sz(v);
		sz[u] += sz[v];
		if (f[v]+d[v] > f[u]){
			g[u] = f[u];
			f[u] = f[v]+d[v];
		}
		else if (f[v]+d[v] > g[u]){
			g[u] = f[v]+d[v];
		}
	}
	cur += 2*sumd[u];
}

void build_sparse(){
	for (int i = 1; i <= n; i++) jump[i][0] = p[i];
	for (int j = 1; j <= LOG; j++)
		for (int i = 1; i <= n; i++)
			jump[i][j] = jump[jump[i][j-1]][j-1];
}

void dfs_hld(int u){
	tin[u] = ++timer;
	tour[timer] = u;
	int mxVtx = -1;
	for (int v : son[u]){
		if (mxVtx == -1 || sz[v] > sz[mxVtx]) mxVtx = v;
	}
	if (mxVtx != -1){
		head[mxVtx] = head[u];
		dfs_hld(mxVtx);
	}
	for (int v : son[u]){
		if (v == mxVtx) continue;
		head[v] = v;
		dfs_hld(v);
	}
	tout[u] = timer;
}

node operator + (node a, node b){
	node c;
	c.sz = a.sz+b.sz;
	c.f = a.f+b.f;
	c.g = a.g+b.g;
	return c;
}

void build(int id, int l, int r){
	if (l == r){
		int u = tour[l];
		st[id].sz = 1;
		st[id].f = f[u]+sumd[u];
		st[id].g = g[u]+sumd[u];
		return;
	}
	int mid = (l+r)/2;
	build(2*id, l, mid);
	build(2*id+1, mid+1, r);
	st[id] = st[2*id]+st[2*id+1];
}

void apply(int id, tag T){
	if (T.f.fi == 1) st[id].f += T.f.se*st[id].sz; else st[id].f = T.f.se*st[id].sz;
	if (T.g.fi == 1) st[id].g += T.g.se*st[id].sz; else st[id].g = T.g.se*st[id].sz;
}

pii operator + (pii a, pii b){
	pii c;
	if (b.fi == 2) c = mp(2, b.se);
	else if (a.fi == 2) c = mp(2, a.se+b.se);
	else c = mp(1, a.se+b.se);
	return c;
}

tag operator + (tag a, tag b){
	tag c;
	c.f = a.f+b.f;
	c.g = a.g+b.g;
	return c;
}

void down(int id){
	apply(2*id, lazy[id]); apply(2*id+1, lazy[id]);
	lazy[2*id] = lazy[2*id]+lazy[id]; lazy[2*id+1] = lazy[2*id+1]+lazy[id];
	lazy[id] = tag();
}

void swap(int id, int l, int r, int i){
	if (i < l || i > r) return;
	if (l == r){
		swap(st[id].f, st[id].g);
		return;
	}
	down(id);
	int mid = (l+r)/2;
	swap(2*id, l, mid, i);
	swap(2*id+1, mid+1, r, i);
	st[id] = st[2*id]+st[2*id+1];
}

void cover(int id, int l, int r, int u, int v, pii P){
	if (v < l || u > r) return;
	if (l >= u && r <= v){
		pii x = mp(1, 0), y = mp(1, 0);
		if (P.fi != -1) x = mp(2, P.fi);
		if (P.se != -1) y = mp(2, P.se);
		tag T = tag(x, y);
		apply(id, T);
		lazy[id] = lazy[id]+T;
		return;
	}
	down(id);
	int mid = (l+r)/2;
	cover(2*id, l, mid, u, v, P);
	cover(2*id+1, mid+1, r, u, v, P);
	st[id] = st[2*id]+st[2*id+1];
}

void add(int id, int l, int r, int u, int v, pii P){
	if (v < l || u > r) return;
	if (l >= u && r <= v){
		tag T = tag(mp(1, P.fi), mp(1, P.se));
		apply(id, T);
		lazy[id] = lazy[id]+T;
		return;
	}
	down(id);
	int mid = (l+r)/2;
	add(2*id, l, mid, u, v, P);
	add(2*id+1, mid+1, r, u, v, P);
	st[id] = st[2*id]+st[2*id+1];
}

node get(int id, int l, int r, int i){
	if (l == r) return st[id];
	down(id);
	int mid = (l+r)/2;
	if (i <= mid) return get(2*id, l, mid, i);
	return get(2*id+1, mid+1, r, i);
}

void buff_f(int u, int a, int val){
	while (true){
		if (head[u] == head[a]){
			cover(1, 1, n, tin[a], tin[u], mp(val, -1));
			break;
		}
		cover(1, 1, n, tin[head[u]], tin[u], mp(val, -1));
		u = p[head[u]];
	}
}

void update(int u, int su, int a, int val){
	if (u == 0 || dep[u] < dep[a]) return;
	vector <int> arr = {};
	while (true){
		if (get(1, 1, n, tin[u]).f == get(1, 1, n, tin[su]).f){
			int v = u, tmp = get(1, 1, n, tin[su]).f;
			for (int i = LOG; i >= 0; i--){
				if (jump[v][i] == 0 || dep[jump[v][i]] < dep[a]) continue;
				if (get(1, 1, n, tin[jump[v][i]]).f == tmp) v = jump[v][i];
			}
			buff_f(u, v, val);
			u = p[v];
		}
		if (u == 0 || dep[u] < dep[a]) break;
		arr.push_back(u);
		su = u;
		u = p[u];
	}
	for (int u : arr){
		swap(1, 1, n, tin[u]);
		cover(1, 1, n, tin[u], tin[u], mp(val, -1));
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i = 2; i <= n; i++){
		cin >> p[i];
		p[i]++;
		son[p[i]].push_back(i);
	}
	for (int i = 2; i <= n; i++){
		cin >> d[i];
	}
	dfs_sz(1);
	build_sparse();
	head[1] = 1;
	dfs_hld(1);
	build(1, 1, n);
	
	cout << (st[1].f+st[1].g-cur)%MOD << '\n';
	cin >> q;
	while (q--){
		int x, y; cin >> x >> y;
		x++;
		cur += 2*sz[x]*y;
		int u = x, tmp = get(1, 1, n, tin[x]).f+y;
		for (int i = LOG; i >= 0; i--){
			if (jump[u][i] == 0) continue;
			if (tmp > get(1, 1, n, tin[jump[u][i]]).f) u = jump[u][i];
		}
		update(p[x], x, u, tmp);
		u = p[u];
		if (u > 0 && tmp > get(1, 1, n, tin[u]).g){
			cover(1, 1, n, tin[u], tin[u], mp(-1, tmp));
		}
		add(1, 1, n, tin[x], tout[x], mp(y, y));
		cout << (st[1].f+st[1].g-cur)%MOD << '\n';
	}
	return 0;
}

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