10509 2024. 04. 03 20:22:30 111 John's Gardening Invention cpp17 Elfogadva 100/100 785ms 177808 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

#define INF (int)1e16

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,Q;
	cin>>N>>Q;
	vector<vector<int>>g(N+1);
	for(int a=1;a<=N;a++){
		int b;
		cin>>b;
		b++;
		g[a].push_back(b);
		g[b].push_back(a);
		// cout<<a<<' '<<b<<endl;
	}
	int R=g[0][0];
	vector<int>c(N+1);
	for(int i=1;i<=N;i++){
		cin>>c[i];
	}
	vector<int>s(N+1);
	for(int i=1;i<=N;i++){
		cin>>s[i];
	}
	vector<int>c0(N+1),c1(N+1),c2(N+1);
	auto dfs1=[&](auto self,int i,int p)->void{
		c0[i]=!s[i]?0:c[i];
		c1[i]=!s[i]?c[i]:0;
		c2[i]=0;
		for(int j:g[i]){
			if(j==p){
				continue;
			}
			self(self,j,i);
			c1[i]+=c0[j];
		}
		if(g[i].size()>1){
			c0[i]=min(c0[i],c1[i]);
		}
		for(int j:g[i]){
			if(j==p){
				continue;
			}
			c2[j]+=c1[i]-c0[j];
		}
	};
	dfs1(dfs1,R,0);
	vector<int>ti(N+1),to(N+1);
	vector<array<int,20>>u(N+1),o(N+1);
	int ta=0;
	auto dfs2=[&](auto self,int i,int p)->void{
		ti[i]=++ta;
		u[i][0]=p;
		o[i][0]=c2[i];
		for(int j=1;j<20;j++){
			u[i][j]=u[u[i][j-1]][j-1];
			o[i][j]=o[u[i][j-1]][j-1]+o[i][j-1];
		}
		for(int j:g[i]){
			if(j==p){
				continue;
			}
			self(self,j,i);
		}
		to[i]=++ta;
	};
	ti[0]=++ta;
	dfs2(dfs2,R,0);
	to[0]=++ta;
	auto des=[&](int a,int b)->bool{
		return ti[a]<=ti[b]&&to[a]>=to[b];
	};
	auto lca=[&](int a,int b)->int{
		while(!des(a,b)){
			for(int i=1;i<20;i++){
				if(des(u[a][i],b)){
					a=u[a][i-1];
					break;
				}
			}
		}
		return a;
	};
	auto cost=[&](int a,int b)->int{
		if(a==b){
			return 0;
		}
		int cc=0;
		while(a!=u[b][0]){
			for(int i=1;i<20;i++){
				if(des(u[b][i],a)){
					cc+=o[b][i-1];
					b=u[b][i-1];
					break;
				}
			}
		}
		cc-=c0[b];
		return cc;
	};
	while(Q--){
		int M;
		cin>>M;
		vector<int>v(M);
		for(int i=0;i<M;i++){
			cin>>v[i];
			v[i]++;
		}
		if(M==0){
			cout<<c0[R]<<'\n';
			continue;
		}
		int ans=0;
		sort(v.begin(),v.end(),[&](int a,int b){return ti[a]<ti[b];});
		vector<int>s;
		s.push_back(R);
		v.push_back(R);
		for(int i:v){
			while(!des(s.back(),i)){
				int b=s.back();
				s.pop_back();
				int l=lca(b,i);
				if(des(l,s.back())){
					ans+=cost(s.back(),b);
				}
				else{
					ans+=cost(l,b);
					ans+=c1[l];
					s.push_back(l);
				}
			}
			ans+=c1[i];
			s.push_back(i);
		}
		cout<<ans<<'\n';
	}
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1832 KiB
subtask2 8/8
2 Elfogadva 3ms 2056 KiB
3 Elfogadva 3ms 2264 KiB
subtask3 11/11
4 Elfogadva 3ms 2452 KiB
5 Elfogadva 3ms 2680 KiB
6 Elfogadva 3ms 2772 KiB
7 Elfogadva 3ms 2856 KiB
8 Elfogadva 3ms 2940 KiB
subtask4 30/30
9 Elfogadva 9ms 7164 KiB
10 Elfogadva 9ms 6904 KiB
11 Elfogadva 8ms 7424 KiB
12 Elfogadva 10ms 7480 KiB
13 Elfogadva 10ms 7380 KiB
14 Elfogadva 8ms 7376 KiB
15 Elfogadva 8ms 7376 KiB
16 Elfogadva 10ms 7344 KiB
17 Elfogadva 10ms 7324 KiB
18 Elfogadva 10ms 7456 KiB
19 Elfogadva 9ms 7448 KiB
subtask5 51/51
20 Elfogadva 504ms 177808 KiB
21 Elfogadva 523ms 175828 KiB
22 Elfogadva 324ms 177116 KiB
23 Elfogadva 628ms 175336 KiB
24 Elfogadva 477ms 175008 KiB
25 Elfogadva 421ms 176328 KiB
26 Elfogadva 541ms 174564 KiB
27 Elfogadva 523ms 174972 KiB
28 Elfogadva 465ms 176188 KiB
29 Elfogadva 606ms 174472 KiB
30 Elfogadva 512ms 174900 KiB
31 Elfogadva 428ms 176204 KiB
32 Elfogadva 625ms 174480 KiB
33 Elfogadva 714ms 174512 KiB
34 Elfogadva 751ms 174648 KiB
35 Elfogadva 785ms 175012 KiB
36 Elfogadva 367ms 175520 KiB
37 Elfogadva 342ms 175468 KiB
38 Elfogadva 324ms 175316 KiB
39 Elfogadva 523ms 175004 KiB
40 Elfogadva 671ms 174976 KiB
41 Elfogadva 300ms 175616 KiB