105092024-04-03 20:22:30111John's Gardening Inventioncpp17Accepted 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1832 KiB
subtask28/8
2Accepted3ms2056 KiB
3Accepted3ms2264 KiB
subtask311/11
4Accepted3ms2452 KiB
5Accepted3ms2680 KiB
6Accepted3ms2772 KiB
7Accepted3ms2856 KiB
8Accepted3ms2940 KiB
subtask430/30
9Accepted9ms7164 KiB
10Accepted9ms6904 KiB
11Accepted8ms7424 KiB
12Accepted10ms7480 KiB
13Accepted10ms7380 KiB
14Accepted8ms7376 KiB
15Accepted8ms7376 KiB
16Accepted10ms7344 KiB
17Accepted10ms7324 KiB
18Accepted10ms7456 KiB
19Accepted9ms7448 KiB
subtask551/51
20Accepted504ms177808 KiB
21Accepted523ms175828 KiB
22Accepted324ms177116 KiB
23Accepted628ms175336 KiB
24Accepted477ms175008 KiB
25Accepted421ms176328 KiB
26Accepted541ms174564 KiB
27Accepted523ms174972 KiB
28Accepted465ms176188 KiB
29Accepted606ms174472 KiB
30Accepted512ms174900 KiB
31Accepted428ms176204 KiB
32Accepted625ms174480 KiB
33Accepted714ms174512 KiB
34Accepted751ms174648 KiB
35Accepted785ms175012 KiB
36Accepted367ms175520 KiB
37Accepted342ms175468 KiB
38Accepted324ms175316 KiB
39Accepted523ms175004 KiB
40Accepted671ms174976 KiB
41Accepted300ms175616 KiB