106202024-04-06 22:56:51111Őslényországcpp17Accepted 100/100620ms270428 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

struct Fenwick{
	int n;
	vector<int>t;
	
	Fenwick(int n):n(n+1),t(n+1){
	}
	
	void add(int i,int x){
		for(i++;i<n;i+=i&-i){
			t[i]+=x;
		}
	}
	
	void add(int l,int r,int x){
		add(l,x);
		add(r+1,-x);
	}
	
	int get(int i){
		int x=0;
		for(i++;i;i-=i&-i){
			x+=t[i];
		}
		return x;
	}
};

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	cin>>N;
	vector<vector<int>>g1(N+1);
	for(int i=2;i<=N;i++){
		int p;
		cin>>p;
		g1[p].push_back(i);
	}
	int M;
	cin>>M;
	vector<vector<int>>g2(M+1);
	for(int i=2;i<=M;i++){
		int p;
		cin>>p;
		g2[p].push_back(i);
	}
	vector<vector<pair<int,int>>>v(N+1),q(N+1);
	int K;
	cin>>K;
	for(int i=0;i<K;i++){
		int a,b,c;
		cin>>a>>b>>c;
		v[a].emplace_back(b,c);
	}
	int Q;
	cin>>Q;
	for(int i=0;i<Q;i++){
		int a,b;
		cin>>a>>b;
		q[a].emplace_back(b,i);
	}
	vector<int>ti(M+1),to(M+1);
	int t=0;
	auto dfs=[&](auto self,int i)->void{
		ti[i]=t++;
		for(int j:g2[i]){
			self(self,j);
		}
		to[i]=t++;
	};
	dfs(dfs,1);
	Fenwick f(t);
	vector<int>ans(Q);
	auto dfs1=[&](auto self,int i)->void{
		for(auto[j,c]:v[i]){
			f.add(ti[j],to[j],c);
		}
		for(auto[j,k]:q[i]){
			ans[k]=f.get(ti[j]);
		}
		for(int j:g1[i]){
			self(self,j);
		}
		for(auto[j,c]:v[i]){
			f.add(ti[j],to[j],-c);
		}
	};
	dfs1(dfs1,1);
	for(int i=0;i<Q;i++){
		cout<<ans[i]<<'\n';
	}
	cout<<'\n';
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1824 KiB
subtask215/15
2Accepted3ms2260 KiB
3Accepted3ms2544 KiB
4Accepted4ms3024 KiB
5Accepted4ms3300 KiB
6Accepted4ms3688 KiB
7Accepted4ms3876 KiB
8Accepted4ms4100 KiB
9Accepted4ms4132 KiB
subtask330/30
10Accepted247ms71588 KiB
11Accepted203ms60740 KiB
12Accepted351ms120036 KiB
13Accepted338ms113476 KiB
14Accepted375ms159620 KiB
15Accepted349ms139660 KiB
subtask425/25
16Accepted592ms170196 KiB
17Accepted620ms201624 KiB
18Accepted504ms210644 KiB
19Accepted462ms191668 KiB
20Accepted589ms228836 KiB
21Accepted513ms243588 KiB
subtask530/30
22Accepted582ms224092 KiB
23Accepted476ms233176 KiB
24Accepted469ms235272 KiB
25Accepted458ms240792 KiB
26Accepted492ms270428 KiB