105082024-04-03 20:09:37111John's Gardening Inventioncpp17Wrong answer 8/100735ms291476 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+=c1[l];
					s.push_back(l);
				}
			}
			ans+=c1[i];
			s.push_back(i);
		}
		cout<<ans<<'\n';
	}
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1836 KiB
subtask28/8
2Accepted3ms2040 KiB
3Accepted3ms2264 KiB
subtask30/11
4Wrong answer3ms2660 KiB
5Wrong answer3ms2548 KiB
6Wrong answer3ms2436 KiB
7Wrong answer3ms2652 KiB
8Wrong answer3ms2860 KiB
subtask40/30
9Wrong answer9ms7380 KiB
10Wrong answer9ms7204 KiB
11Wrong answer8ms7868 KiB
12Wrong answer9ms7960 KiB
13Wrong answer10ms8084 KiB
14Wrong answer8ms8140 KiB
15Wrong answer9ms8532 KiB
16Wrong answer12ms8452 KiB
17Wrong answer10ms8496 KiB
18Wrong answer10ms8632 KiB
19Wrong answer9ms8768 KiB
subtask50/51
20Wrong answer504ms185660 KiB
21Wrong answer621ms190488 KiB
22Wrong answer328ms198660 KiB
23Wrong answer735ms203936 KiB
24Wrong answer580ms209800 KiB
25Wrong answer425ms217048 KiB
26Wrong answer629ms221424 KiB
27Wrong answer619ms228488 KiB
28Wrong answer460ms236328 KiB
29Wrong answer691ms241344 KiB
30Wrong answer521ms248636 KiB
31Wrong answer435ms256876 KiB
32Wrong answer593ms262024 KiB
33Wrong answer672ms269124 KiB
34Wrong answer720ms276020 KiB
35Wrong answer731ms283484 KiB
36Wrong answer372ms290980 KiB
37Wrong answer342ms291244 KiB
38Wrong answer326ms291112 KiB
39Wrong answer597ms290784 KiB
40Wrong answer639ms290840 KiB
41Wrong answer298ms291476 KiB