105082024-04-03 20:09:37111John's Gardening Inventioncpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1836 KiB
subtask28/8
2Elfogadva3ms2040 KiB
3Elfogadva3ms2264 KiB
subtask30/11
4Hibás válasz3ms2660 KiB
5Hibás válasz3ms2548 KiB
6Hibás válasz3ms2436 KiB
7Hibás válasz3ms2652 KiB
8Hibás válasz3ms2860 KiB
subtask40/30
9Hibás válasz9ms7380 KiB
10Hibás válasz9ms7204 KiB
11Hibás válasz8ms7868 KiB
12Hibás válasz9ms7960 KiB
13Hibás válasz10ms8084 KiB
14Hibás válasz8ms8140 KiB
15Hibás válasz9ms8532 KiB
16Hibás válasz12ms8452 KiB
17Hibás válasz10ms8496 KiB
18Hibás válasz10ms8632 KiB
19Hibás válasz9ms8768 KiB
subtask50/51
20Hibás válasz504ms185660 KiB
21Hibás válasz621ms190488 KiB
22Hibás válasz328ms198660 KiB
23Hibás válasz735ms203936 KiB
24Hibás válasz580ms209800 KiB
25Hibás válasz425ms217048 KiB
26Hibás válasz629ms221424 KiB
27Hibás válasz619ms228488 KiB
28Hibás válasz460ms236328 KiB
29Hibás válasz691ms241344 KiB
30Hibás válasz521ms248636 KiB
31Hibás válasz435ms256876 KiB
32Hibás válasz593ms262024 KiB
33Hibás válasz672ms269124 KiB
34Hibás válasz720ms276020 KiB
35Hibás válasz731ms283484 KiB
36Hibás válasz372ms290980 KiB
37Hibás válasz342ms291244 KiB
38Hibás válasz326ms291112 KiB
39Hibás válasz597ms290784 KiB
40Hibás válasz639ms290840 KiB
41Hibás válasz298ms291476 KiB