Submission #534846

#	Time	Username	Problem	Language	Result	Execution time	Memory
534846		amunduzbaev	Arboras (RMI20_arboras)	C++17	24 / 100	5006 ms	16868 KiB

arboras

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

#define ar array
#define int long long

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
//~ struct ST{
	//~ int tree[N << 2], mn[N << 2], mx[N << 2];
	//~ bool is[N << 2], val[N << 2];
	
	//~ void push(int x, int lx, int rx){
		//~ if(lx == rx || !is[x]) return;
		//~ int m = (lx + rx) >> 1;
		//~ tree[x<<1] = mn[x] % mod * 1ll * (m - lx + 1) % mod;
		//~ tree[x<<1|1] = mn[x] % mod * 1ll * (rx - m) % mod;
		//~ mn[x<<1] = mn[x<<1|1] = mn[x];
		//~ mx[x<<1] = mx[x<<1|1] = mx[x];
		//~ is[x<<1] = is[x<<1|1] = 1;
		//~ is[x] = 0;
	//~ }
	
	//~ void umax(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		//~ if(lx > r || rx < l || mn[x] >= v) return;
		//~ if(lx >= l && rx <= r && mx[x] <= v){
			//~ tree[x] = (rx - lx + 1) * 1ll * (v % mod) % mod;
			//~ mn[x] = mx[x] = v; is[x] = 1;
			//~ return;
		//~ } push(x, lx, rx);
		//~ int m = (lx + rx) >> 1;
		//~ umax(l, r, v, lx, m, x<<1);
		//~ umax(l, r, v, m+1, rx, x<<1|1);
		//~ tree[x] = tree[x<<1] + tree[x<<1|1];
		//~ mn[x] = min(mn[x<<1], mn[x<<1|1]);
		//~ mx[x] = max(mx[x<<1], mx[x<<1|1]);
	//~ }
	
	//~ int get(int i, int lx = 0, int rx = N, int x = 1){
		//~ if(lx == rx) return mx[x];
		//~ push(x, lx, rx);
		//~ int m = (lx + rx) >> 1;
		//~ if(i <= m) return get(i, lx, m, x<<1);
		//~ else return get(i, m+1, rx, x<<1|1);
	//~ }
//~ }tree;

vector<int> edges[N];
int dp[N][2], in[N][2];
int c[N], pp[N];
//~ int hv[N], pos[N], par[N], t;

void dfs(int u){
	in[u][0] = in[u][1] = u;
	dp[u][0] = dp[u][1] = 0;
	for(auto x : edges[u]){
		dfs(x);
		if(dp[x][0] + c[x] > dp[u][1]){
			dp[u][1] = dp[x][0] + c[x];
			in[u][1] = x;
		}
		
		if(dp[u][1] > dp[u][0]){
			swap(dp[u][0], dp[u][1]);
			swap(in[u][0], in[u][1]);
		}
	}
}

//~ void dec(int u){
	//~ pos[u] = t++;
	//~ tree.umax(pos[u], pos[u], dp[u]);
	//~ if(~hv[u]){
		//~ par[hv[u]] = par[u];
		//~ dec(hv[u]);
	//~ }
	
	//~ for(auto x : edges[u]){
		//~ if(x[0] == hv[u]) continue;
		//~ par[x[0]] = x[0];
		//~ dec(x[0]);
	//~ }
//~ }

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	memset(pp, -1, sizeof pp);
	for(int i=1;i<n;i++) cin>>pp[i];
	for(int i=1;i<n;i++){
		cin>>c[i];
		edges[pp[i]].push_back(i);
	}
	
	dfs(0);
	//~ dec(0);
	int res = 0;
	for(int i=0;i<n;i++){
		res += dp[i][0] + dp[i][1];
	}
	cout<<res % mod<<"\n";
	int q; cin>>q;
	while(q--){
		int i, v; cin>>i>>v;
		//~ for(int i=0;i<n;i++) cout<<dp[i][0]<<" "<<dp[i][1]<<"\n";
		c[i] += v;
		while(i){
			int p = pp[i];
			if(in[p][0] == i){
				res = (res - dp[p][0] + dp[i][0] + c[i]);
				dp[p][0] = dp[i][0] + c[i];
			} else {
				if(dp[p][0] < dp[i][0] + c[i]){
					res = (res - dp[p][1] + dp[i][0] + c[i]);
					dp[p][1] = dp[p][0], in[p][1] = in[p][0];
					dp[p][0] = dp[i][0] + c[i], in[p][0] = i;
				} else {
					if(dp[p][1] < dp[i][0] + c[i]){
						res = (res - dp[p][1] + dp[i][0] + c[i]);
						dp[p][1] = dp[i][0] + c[i], in[p][1] = i;
					}
					
					break;
				}
			}
			
			i = p;
		}
		
		cout<<res % mod<<"\n";
	}
}

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