#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005, mod = 998244353;
int n;
int hvy[MAXN], a[MAXN];
long long dp[MAXN];
vector<int> adj[MAXN];
struct FenwickTree{
int bit[MAXN];
void upd(int i, int x){
while (i <= n){
bit[i] += x;
i += i & (-i);
}
}
int sum(int i){
int ans = 0;
while (i){
ans += bit[i];
i -= i & (-i);
}
return ans;
}
int get(int l, int r){
if (l > r) return 0;
return sum(r) - sum(l - 1);
}
}ft;
int node = 1;
void input(){
int x; cin >> x;
a[node] = x;
if (x) return;
int nw = node;
adj[nw].push_back(++node);
input();
adj[nw].push_back(++node);
input();
}
int pre_dfs(int u, int p){
if (adj[u].empty()) leave[u] = 1;
int sz = 1, mx = 0;
for (int v : adj[u]){
if (v != p){
int csz = pre_dfs(v, u);
leave[u] += leave[v];
sz += csz;
if (mx < csz){
mx = csz;
hvy[u] = v;
}
}
}
return sz;
}
void ope(int u, int p, int x){
if (a[u]) ft.upd(a[u], x);
for (int v : adj[u]){
if (v != p) ope(v, u, x);
}
}
long long c1, c2;
void calc(int u, int p){
if (a[u]){
c1 += ft.get(a[u] + 1, n);
c2 += ft.get(1, a[u] - 1);
}
for (int v : adj[u]){
if (v != p) calc(v, u);
}
}
void dfs(int u, int p){
for (int &v : adj[u]){
if (v != p && v != hvy[u]){
dfs(v, u);
dp[u] += dp[v];
ope(v, u, -1);
}
}
if (hvy[u]){
dfs(hvy[u], u);
dp[u] += dp[hvy[u]];
}
c1 = c2 = 0;
for (int v : adj[u]){
if (v != p && v != hvy[u]){
calc(v, u);
}
}
dp[u] += min(c1, c2);
for (int v : adj[u]){
if (v != p && v != hvy[u]){
ope(v, u, 1);
}
}
if (a[u]) ft.upd(a[u], 1);
}
void solve(){
cin >> n;
input();
pre_dfs(1, 1);
dfs(1, 1);
cout << dp[1];
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1; // cin >> t;
while (t--){
solve();
}
}
Compilation message
rot.cpp: In function 'int pre_dfs(int, int)':
rot.cpp:44:23: error: 'leave' was not declared in this scope
44 | if (adj[u].empty()) leave[u] = 1;
| ^~~~~
rot.cpp:49:7: error: 'leave' was not declared in this scope
49 | leave[u] += leave[v];
| ^~~~~
