#include <iostream>
#include <vector>
using namespace std;
int N;
vector<int> gph[202020];
int par[202020];
int in[202020];
int rev[202020];
int sz[202020];
int dep[202020];
int up[202020];
int icnt = 0;
void dfs2(int x)
{
sz[x] = 1;
for(int i = 0; i < (int)gph[x].size(); ++i)
{
dfs2(gph[x][i]);
sz[x] += sz[gph[x][i]];
if(sz[gph[x][0]] < sz[gph[x][i]]) swap(gph[x][0], gph[x][i]);
}
}
void dfs3(int x, int d, int u)
{
dep[x] = d;
up[x] = u;
in[x] = icnt++;
for(int i = 0; i < (int)gph[x].size(); ++i)
dfs3(gph[x][i], d + 1, i ? gph[x][i] : u);
}
const int INF = (int)1e9 + 7;
struct Node
{
int mx[2], mn[2], lazy[2];
Node(void) { mx[0] = mx[1] = -INF; mn[0] = mn[1] = INF; lazy[0] = lazy[1] = 0; }
}seg[808080];
void prop(int ind)
{
for(auto x : {ind << 1, ind << 1 | 1})
{
seg[x].lazy[0] += seg[ind].lazy[0];
seg[x].lazy[1] += seg[ind].lazy[1];
seg[x].mx[0] += seg[ind].lazy[0];
seg[x].mx[1] += seg[ind].lazy[1];
seg[x].mn[0] += seg[ind].lazy[0];
seg[x].mn[1] += seg[ind].lazy[1];
}
seg[ind].lazy[0] = seg[ind].lazy[1] = 0;
}
void mrge(int ind)
{
Node &nd = seg[ind], &x = seg[ind << 1], &y = seg[ind << 1 | 1];
nd.mx[0] = max(x.mx[0], y.mx[0]);
nd.mx[1] = max(x.mx[1], y.mx[1]);
nd.mn[0] = min(x.mn[0], y.mn[0]);
nd.mn[1] = min(x.mn[1], y.mn[1]);
}
void upd(int ind, int s, int e, int l, int r, int x)
{
if(e <= l || r <= s) return;
if(l <= s && e <= r)
{
seg[ind].mx[0] += x;
seg[ind].mx[1] -= x;
seg[ind].mn[0] += x;
seg[ind].mn[1] -= x;
seg[ind].lazy[0] += x;
seg[ind].lazy[1] -= x;
return;
}
prop(ind);
int mid = s + e >> 1;
upd(ind << 1, s, mid, l, r, x);
upd(ind << 1 | 1, mid, e, l, r, x);
mrge(ind);
}
void updp(int ind, int s, int e, int pos, bool f)
{
if(s + 1 == e)
{
if(f) seg[ind].mn[0] = seg[ind].mx[0] = 0;
else seg[ind].mn[1] = seg[ind].mx[1] = 0;
return;
}
prop(ind);
int mid = s + e >> 1;
if(pos < mid) updp(ind << 1, s, mid, pos, f);
else updp(ind << 1 | 1, mid, e, pos, f);
mrge(ind);
}
int lb(int ind, int s, int e, int l, int r, int ev, int od)
{
if(e <= l || r <= s) return -1;
if(l <= s && e <= r && seg[ind].mn[0] >= ev && seg[ind].mn[1] >= od && seg[ind].mx[0] <= ev && seg[ind].mx[1] <= od) return -1;
if(s + 1 == e) return s;
prop(ind);
int mid = s + e >> 1;
int t = lb(ind << 1 | 1, mid, e, l, r, ev, od);
if(t != -1) return t;
return lb(ind << 1, s, mid, l, r, ev, od);
}
int qry(int x, int k)
{
int t = lb(1, 0, N, in[up[x]], in[x] + 1, (in[x] & 1 ? 1 - k : k), (in[x] & 1 ? k : 1 - k));
int ret = in[x] - (t == -1 ? in[up[x]] - 1 : t);
upd(1, 0, N, (t == -1 ? in[up[x]] : t), in[x] + 1, (in[x] & 1 ? 2 * k - 1 : 1 - 2 * k));
if(t != -1 || up[x] == 0) return ret;
return ret + qry(par[up[x]], ((in[x] - in[up[x]]) & 1) ? k : 1 - k);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("input.txt", "r", stdin);
int n; cin >> n;
N = n + 1;
for(int i = 1; i <= n; ++i)
{
int x; cin >> x;
par[i] = x;
gph[x].push_back(i);
}
dfs2(0);
dfs3(0, 0, 0);
for(int i = 0; i < n; ++i) rev[in[i]] = i;
for(int i = 1; i <= n; ++i)
{
updp(1, 0, N, i - 1, ~in[i - 1] & 1);
cout << qry(par[i], 0) << '\n';
}
}
Compilation message
Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:79:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
79 | int mid = s + e >> 1;
| ~~^~~
Main.cpp: In function 'void updp(int, int, int, int, bool)':
Main.cpp:94:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | int mid = s + e >> 1;
| ~~^~~
Main.cpp: In function 'int lb(int, int, int, int, int, int, int)':
Main.cpp:106:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
106 | int mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
24072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
24072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
24072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
945 ms |
32316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
24072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
