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 |