Submission #1297672

#TimeUsernameProblemLanguageResultExecution timeMemory
1297672NotLinuxArboras (RMI20_arboras)C++20
0 / 100
42 ms10952 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
const int mod = 1e9 + 7;
int fastpow(int a , int b){
	int ret = 1;
	while(b){
		if(b&1)ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}
void solve(){
	int n;
	cin >> n;
	int p[n] , d[n];
	for(int i = 1;i<n;i++)cin >> p[i];
	for(int i = 1;i<n;i++)cin >> d[i];
	vector<int>tree[n];
	for(int i = 1;i<n;i++){
		tree[p[i]].push_back(i);
	}
	vector<int>add(n,0);
	function<pair<int,int>(int,int)> dfs = [&](int node , int par){
		if(tree[node].empty()){
			return pair<int,int>{0,node};
		}
		vector<pair<int,int>>v;
		for(auto itr : tree[node]){
			v.push_back(dfs(itr,node));
		}
		sort(all(v));

		if(sz(tree[node]) == 1){
			add[v[sz(v)-1].second]++;
			add[node]--;
			// cout << "added : " << v[sz(v)-1].second << " -> " << par << endl;
		}
		else{
			add[v[sz(v)-1].second]++;
			add[v[sz(v)-2].second]++;
			add[node]-=2;
			// cout << "added : " << v[sz(v)-1].second << " -> " << v[sz(v)-2].second << endl;
		}

		return pair<int,int>{v.back().first+1 , v.back().second};
	};
	dfs(0,-1);
	function<void(int)> dfs2 = [&](int node){
		for(auto itr : tree[node]){
			dfs2(itr);
			add[node] += add[itr];
		}
	};
	// cout << "add : ";for(int i = 0;i<n;i++)cout << add[i] << " ";cout << endl;
	dfs2(0);
	// cout << "add : ";for(int i = 0;i<n;i++)cout << add[i] << " ";cout << endl;
	int ans = 0;
	for(int i = 0;i<n;i++){
		ans = (ans + add[i] * d[i] % mod) % mod;
	}
	int q;
	cin >> q;
	cout << ans << '\n';
	while(q--){
		int node , ekle;
		cin >> node >> ekle;
		ans = (ans + add[node] * ekle % mod) % mod;
		cout << ans << '\n';
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase=1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...