106202024-04-06 22:56:51111Őslényországcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1824 KiB
subtask215/15
2Elfogadva3ms2260 KiB
3Elfogadva3ms2544 KiB
4Elfogadva4ms3024 KiB
5Elfogadva4ms3300 KiB
6Elfogadva4ms3688 KiB
7Elfogadva4ms3876 KiB
8Elfogadva4ms4100 KiB
9Elfogadva4ms4132 KiB
subtask330/30
10Elfogadva247ms71588 KiB
11Elfogadva203ms60740 KiB
12Elfogadva351ms120036 KiB
13Elfogadva338ms113476 KiB
14Elfogadva375ms159620 KiB
15Elfogadva349ms139660 KiB
subtask425/25
16Elfogadva592ms170196 KiB
17Elfogadva620ms201624 KiB
18Elfogadva504ms210644 KiB
19Elfogadva462ms191668 KiB
20Elfogadva589ms228836 KiB
21Elfogadva513ms243588 KiB
subtask530/30
22Elfogadva582ms224092 KiB
23Elfogadva476ms233176 KiB
24Elfogadva469ms235272 KiB
25Elfogadva458ms240792 KiB
26Elfogadva492ms270428 KiB