ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#206242 | #2646. sum | three_zero30 | 100 | 1950ms | 11488kb | C++11 | 1.1kb | 2024-07-21 16:05:39 | 2024-07-21 16:42:58 |
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+2;
int fa[N],n,x,m,cmd;
struct node{
bool f;
int count;
vector<int> sons;
};
node nd[N];
int start_dfs(int x){
if(nd[x].sons.empty()){
nd[x].count=nd[x].f;
return nd[x].count;
}
nd[x].count=nd[x].f;
for(auto v:nd[x].sons)nd[x].count+=start_dfs(v);
return nd[x].count;
}
int update(int x){
if(nd[x].sons.empty()){
nd[x].f=!nd[x].f;
nd[x].count=nd[x].f;
return nd[x].count;
}
nd[x].f=!nd[x].f;
nd[x].count=nd[x].f;
for(auto v:nd[x].sons)nd[x].count+=update(v);
return nd[x].count;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
fa[1]=0;
for(int i=1;i<n;i++){
cin>>x;
nd[x].sons.push_back(i+1);
fa[i+1]=x;
}
for(int i=1;i<=n;i++)cin>>nd[i].f;
start_dfs(1);
cin>>m;
while(m--){
cin>>cmd>>x;
if(cmd==1){
cout<<nd[x].count<<'\n';
}
else{
update(x);
while(1){
x=fa[x];
if(x==0)break;
nd[x].count=nd[x].f;
for(auto v:nd[x].sons){
nd[x].count+=(nd[v].count);
}
}
}
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 345ms
memory: 11292kb
input:
187361 1 1 2 1 3 4 1 3 7 9 2 5 13 8 11 6 13 4 2 12 17 15 21 13 5 9 20 12 4 20 20 22 33 14 33 32 24 9...
output:
3 2 3 0 8 1 0 0 0 0 3 0 0 15 2 1 0 0 5 0 0 0 2 7 0 1 1 1 1 6 3 0 1 1 2 1 6 0 1 10 16 1 1 0 4 1 14 0 ...
result:
ok 92174 lines
Test #2:
score: 10
Accepted
time: 195ms
memory: 11160kb
input:
180975 1 2 3 1 4 1 1 7 6 2 9 9 3 3 11 8 2 6 10 3 4 15 13 24 3 11 9 28 1 28 21 28 33 29 17 15 22 8 39...
output:
0 0 1 0 0 0 0 1 5 3 0 2 1 1 1 1 0 2 1 1 1 6 31 3 1 1 3 1 0 0 0 1 1 1 1 0 0 1 27 0 1 1 1 1 0 3 68 0 1...
result:
ok 96855 lines
Test #3:
score: 10
Accepted
time: 180ms
memory: 11488kb
input:
197782 1 2 3 1 3 2 2 5 5 7 7 4 11 7 3 9 9 16 13 5 18 15 9 21 2 9 7 8 14 17 22 15 16 32 31 33 21 37 3...
output:
1 2 12 0 2 1 1 0 2 1 7 3 2 1 3 0 0 2 0 10 0 4 1 0 1 0 1 3 1 5 1 2 2 0 4 0 0 0 1 1 0 1 0 3 2 1 0 15 1...
result:
ok 94716 lines
Test #4:
score: 10
Accepted
time: 149ms
memory: 11440kb
input:
194589 1 1 1 2 2 3 2 3 5 5 5 6 6 12 3 10 16 8 18 14 12 15 10 11 1 10 15 3 27 6 22 2 32 1 23 15 20 7 ...
output:
1 1 2 2 1 0 3 4 2 4 2 5 0 1 0 0 1 1 0 0 0 2 0 1 0 2 1 1 3 1 1 1 34 0 1 2 1 1 2 2 0 5 1 0 1 0 3 2 1 0...
result:
ok 92131 lines
Test #5:
score: 10
Accepted
time: 188ms
memory: 11308kb
input:
188203 1 2 2 2 5 6 3 6 4 8 2 10 9 7 10 12 5 10 7 18 19 15 2 22 2 9 21 19 24 21 24 8 32 16 29 34 18 6...
output:
0 3 3 1 2 2 1 0 1 2 13 1 4 1 1 1 2 2 0 0 0 1 1 0 0 1 0 1 3 1 1 0 0 0 0 1 11 1 2 2 0 3 3 0 1 0 27 1 1...
result:
ok 97304 lines
Test #6:
score: 10
Accepted
time: 193ms
memory: 11248kb
input:
185010 1 2 2 2 4 1 3 4 4 3 11 12 4 11 10 13 4 1 12 7 13 15 21 19 1 10 2 14 8 10 25 27 15 19 21 16 17...
output:
1 2 0 2 2 1 0 1 3 2 0 12 1 0 0 3 3 0 0 4 0 0 0 0 1 1 0 1 2 0 0 4 1 2 1 1 0 4 1 4 13 1 0 1 1 1 1 1 2 ...
result:
ok 93162 lines
Test #7:
score: 10
Accepted
time: 167ms
memory: 11176kb
input:
181817 1 1 3 3 3 3 3 2 3 1 9 2 12 2 10 14 11 11 15 9 6 15 17 9 25 11 27 22 28 29 25 14 31 31 35 34 1...
output:
22 1 3 1 1 1 5 1 3 0 3 1 0 1 1 1 0 6 3 0 1 1 0 1 0 2 2 4 2 1 0 0 0 1 0 3 1 0 0 1 0 1 1 2 1 0 0 12 2 ...
result:
ok 90816 lines
Test #8:
score: 10
Accepted
time: 180ms
memory: 11452kb
input:
195431 1 1 1 3 1 5 4 6 3 4 5 6 2 11 2 16 17 13 6 20 14 15 14 20 23 10 6 25 25 14 27 20 31 3 19 17 14...
output:
1 1 1 0 0 0 1 5 2 2 3 1 0 0 11 0 1 0 1 0 0 1 8 2 1 0 1 2 1 3 0 0 2 1 0 1 0 1 0 1 21 3 2 4 6 2 1 0 1 ...
result:
ok 96235 lines
Test #9:
score: 10
Accepted
time: 181ms
memory: 11384kb
input:
192238 1 2 1 3 5 1 4 4 2 9 3 8 10 1 2 1 7 5 9 2 8 16 10 17 22 11 14 5 9 3 28 7 14 15 33 35 13 16 1 3...
output:
4 1 3 1 1 1 1 0 1 53 11 3 0 1 0 1 0 3 0 0 0 0 0 3 0 3 0 3 1 1 1 1 1 1 1 1 3 0 0 0 0 0 0 1 1 1 73 1 1...
result:
ok 93875 lines
Test #10:
score: 10
Accepted
time: 172ms
memory: 11324kb
input:
189045 1 2 1 3 4 2 4 2 2 7 2 10 5 6 9 2 6 15 14 4 1 16 6 7 21 9 12 13 22 22 28 26 30 18 25 17 12 24 ...
output:
0 0 3 4 5 0 1 2 0 1 0 1 0 0 1 2 7 0 1 0 0 1 1 5 0 7 41 1 1 11 2 1 1 4 1 0 0 2 0 1 0 1 2 0 0 1 0 0 1 ...
result:
ok 91766 lines