10816 | 2024-04-15 18:01:06 | Valaki2 | Gyors utak | cpp17 | Accepted 100/100 | 194ms | 36088 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 1e5 + 7;
int n, q;
int par[1 + maxn];
vector<int> graph[1 + maxn];
int val[1 + maxn];
int dist[1 + maxn];
int in[1 + maxn];
int ending[1 + maxn];
int timer;
int tree[1 + 4 * maxn];
int lazy[1 + 4 * maxn];
void build(int v, int vl, int vr) {
if(vl == vr) {
tree[v] = dist[vl];
} else {
int mid = (vl + vr) / 2;
build(2 * v, vl, mid);
build(2 * v + 1, mid + 1, vr);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
}
void prop(int v, int vl, int vr) {
if(lazy[v] != 0) {
if(vl != vr) {
lazy[2 * v] ^= 1;
lazy[2 * v + 1] ^= 1;
}
tree[v] = (vr - vl + 1) - tree[v];
lazy[v] = 0;
}
}
void update(int v, int vl, int vr, int ul, int ur) {
//cout << v << " " << vl << " " << vr << "\n";
prop(v, vl, vr);
if(ul > vr || ur < vl) {
return;
}
if(vl == ul && vr == ur) {
lazy[v] ^= 1;
prop(v, vl, vr);
return;
}
prop(v, vl, vr);
int mid = (vl + vr) / 2;
update(2 * v, vl, mid, ul, min(ur, mid));
update(2 * v + 1, mid + 1, vr, max(ul, mid + 1), ur);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
void dfs_euler(int cur) {
timer++;
in[cur] = timer;
for(int nei : graph[cur]) {
dfs_euler(nei);
}
ending[cur] = timer;
}
void solve() {
cin >> n >> q;
for(int i = 2; i <= n; i++) {
cin >> par[i];
graph[par[i]].pb(i);
}
dfs_euler(1);
for(int i = 2; i <= n; i++) {
cin >> val[i];
dist[in[i]] = dist[in[par[i]]] ^ val[i];
}
build(1, 1, n);
/*for(int i = 1; i <= n; i++) {
cout << dist[i] << " " << ending[i] << "\n";
}*/
for(int qi = 0; qi <= q; qi++) {
if(qi != 0) {
int change;
cin >> change;
change++;
// upd
update(1, 1, n, in[change], ending[change]);
//cout << in[change] << " " << ending[change] << "\n";
}
int ans = 0;
int even_cnt = tree[1];
//cout << "-----\n";
int odd_cnt = n - even_cnt;
ans += even_cnt * (even_cnt - 1) / 2;
ans += odd_cnt * (odd_cnt - 1) / 2;
cout << ans << " ";
}
cout << "\n";
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 4ms | 6700 KiB | ||||
2 | Accepted | 6ms | 7972 KiB | ||||
subtask2 | 10/10 | ||||||
3 | Accepted | 4ms | 7244 KiB | ||||
4 | Accepted | 4ms | 7712 KiB | ||||
5 | Accepted | 4ms | 7796 KiB | ||||
6 | Accepted | 4ms | 7992 KiB | ||||
7 | Accepted | 4ms | 8084 KiB | ||||
8 | Accepted | 4ms | 7992 KiB | ||||
subtask3 | 11/11 | ||||||
9 | Accepted | 4ms | 7244 KiB | ||||
10 | Accepted | 4ms | 7712 KiB | ||||
11 | Accepted | 4ms | 7796 KiB | ||||
12 | Accepted | 4ms | 7992 KiB | ||||
13 | Accepted | 4ms | 8084 KiB | ||||
14 | Accepted | 4ms | 7992 KiB | ||||
15 | Accepted | 7ms | 8588 KiB | ||||
16 | Accepted | 7ms | 8576 KiB | ||||
17 | Accepted | 7ms | 8696 KiB | ||||
18 | Accepted | 7ms | 8576 KiB | ||||
19 | Accepted | 8ms | 8724 KiB | ||||
20 | Accepted | 7ms | 8788 KiB | ||||
21 | Accepted | 8ms | 8908 KiB | ||||
22 | Accepted | 8ms | 8892 KiB | ||||
23 | Accepted | 8ms | 8956 KiB | ||||
24 | Accepted | 7ms | 8936 KiB | ||||
subtask4 | 21/21 | ||||||
25 | Accepted | 175ms | 35868 KiB | ||||
26 | Accepted | 172ms | 35876 KiB | ||||
27 | Accepted | 172ms | 35864 KiB | ||||
28 | Accepted | 175ms | 35880 KiB | ||||
29 | Accepted | 175ms | 36088 KiB | ||||
30 | Accepted | 171ms | 36084 KiB | ||||
subtask5 | 24/24 | ||||||
31 | Accepted | 4ms | 8796 KiB | ||||
32 | Accepted | 13ms | 11252 KiB | ||||
33 | Accepted | 98ms | 28212 KiB | ||||
34 | Accepted | 162ms | 28208 KiB | ||||
subtask6 | 34/34 | ||||||
35 | Accepted | 4ms | 7244 KiB | ||||
36 | Accepted | 4ms | 7712 KiB | ||||
37 | Accepted | 4ms | 7796 KiB | ||||
38 | Accepted | 4ms | 7992 KiB | ||||
39 | Accepted | 4ms | 8084 KiB | ||||
40 | Accepted | 4ms | 7992 KiB | ||||
41 | Accepted | 7ms | 8588 KiB | ||||
42 | Accepted | 7ms | 8576 KiB | ||||
43 | Accepted | 7ms | 8696 KiB | ||||
44 | Accepted | 7ms | 8576 KiB | ||||
45 | Accepted | 8ms | 8724 KiB | ||||
46 | Accepted | 7ms | 8788 KiB | ||||
47 | Accepted | 8ms | 8908 KiB | ||||
48 | Accepted | 8ms | 8892 KiB | ||||
49 | Accepted | 8ms | 8956 KiB | ||||
50 | Accepted | 7ms | 8936 KiB | ||||
51 | Accepted | 175ms | 35868 KiB | ||||
52 | Accepted | 172ms | 35876 KiB | ||||
53 | Accepted | 172ms | 35864 KiB | ||||
54 | Accepted | 175ms | 35880 KiB | ||||
55 | Accepted | 175ms | 36088 KiB | ||||
56 | Accepted | 171ms | 36084 KiB | ||||
57 | Accepted | 4ms | 8796 KiB | ||||
58 | Accepted | 13ms | 11252 KiB | ||||
59 | Accepted | 98ms | 28212 KiB | ||||
60 | Accepted | 162ms | 28208 KiB | ||||
61 | Accepted | 173ms | 28792 KiB | ||||
62 | Accepted | 163ms | 27760 KiB | ||||
63 | Accepted | 166ms | 28160 KiB | ||||
64 | Accepted | 165ms | 28224 KiB | ||||
65 | Accepted | 185ms | 29460 KiB | ||||
66 | Accepted | 180ms | 29488 KiB | ||||
67 | Accepted | 184ms | 29772 KiB | ||||
68 | Accepted | 187ms | 29844 KiB | ||||
69 | Accepted | 148ms | 27028 KiB | ||||
70 | Accepted | 187ms | 30260 KiB | ||||
71 | Accepted | 145ms | 26640 KiB | ||||
72 | Accepted | 193ms | 30192 KiB | ||||
73 | Accepted | 194ms | 30412 KiB | ||||
74 | Accepted | 115ms | 30448 KiB | ||||
75 | Accepted | 179ms | 29880 KiB | ||||
76 | Accepted | 181ms | 29996 KiB | ||||
77 | Accepted | 158ms | 28308 KiB |