105092024-04-03 20:22:30111John's Gardening Inventioncpp17Elfogadva 100/100785ms177808 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1832 KiB
subtask28/8
2Elfogadva3ms2056 KiB
3Elfogadva3ms2264 KiB
subtask311/11
4Elfogadva3ms2452 KiB
5Elfogadva3ms2680 KiB
6Elfogadva3ms2772 KiB
7Elfogadva3ms2856 KiB
8Elfogadva3ms2940 KiB
subtask430/30
9Elfogadva9ms7164 KiB
10Elfogadva9ms6904 KiB
11Elfogadva8ms7424 KiB
12Elfogadva10ms7480 KiB
13Elfogadva10ms7380 KiB
14Elfogadva8ms7376 KiB
15Elfogadva8ms7376 KiB
16Elfogadva10ms7344 KiB
17Elfogadva10ms7324 KiB
18Elfogadva10ms7456 KiB
19Elfogadva9ms7448 KiB
subtask551/51
20Elfogadva504ms177808 KiB
21Elfogadva523ms175828 KiB
22Elfogadva324ms177116 KiB
23Elfogadva628ms175336 KiB
24Elfogadva477ms175008 KiB
25Elfogadva421ms176328 KiB
26Elfogadva541ms174564 KiB
27Elfogadva523ms174972 KiB
28Elfogadva465ms176188 KiB
29Elfogadva606ms174472 KiB
30Elfogadva512ms174900 KiB
31Elfogadva428ms176204 KiB
32Elfogadva625ms174480 KiB
33Elfogadva714ms174512 KiB
34Elfogadva751ms174648 KiB
35Elfogadva785ms175012 KiB
36Elfogadva367ms175520 KiB
37Elfogadva342ms175468 KiB
38Elfogadva324ms175316 KiB
39Elfogadva523ms175004 KiB
40Elfogadva671ms174976 KiB
41Elfogadva300ms175616 KiB