#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
using namespace std;
using ll = long long;
const int N = 4e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 , mod = 1e9+7;
int a[N] , ans[N] , n , mxson[N] , cnt[N] , cnt1[N], sz[N] , len;
vector<int> g[N] , vec[N];
void precalc(int v , int pr){
if(v <= n) sz[v] = 1;
for(int to : g[v]){
if(to != pr){
precalc(to,v);
sz[v] += sz[to];
if(sz[to] > sz[mxson[v]]) mxson[v] = to;
}
}
}
void dfs(int v , int pr){
for(int to : g[v]){
if(to != pr && to != mxson[v]) dfs(to,v);
}
if(mxson[v]) {
dfs(mxson[v],v);
vec[v] = vec[mxson[v]];
ans[v] += ans[mxson[v]];
}
int res = 0 , res1 = 0;
for(int to : g[v]){
if(to != pr && to != mxson[v]) {
for(int x : vec[to]){
int pos = vec[v].size()-1;
while(pos > 0 && vec[v][pos] > x) pos--;
res += pos;
res1 += vec[v].size()-(pos);
}
for(int x : vec[to]) vec[v].push_back(x);
ans[v] += ans[to];
}
}
if(v <= n) {
vec[v].push_back(v);
cnt[v] = 1;
cnt1[v/len]++;
}
else {
ans[v] += min(res,res1);
sort(all(vec[v]))
}
}
void go(int num){
int x;
cin >> x;
if(x == 0){
g[num].push_back(num+1);
g[num+1].push_back(num);
go(num+1);
} else {
g[num].push_back(x);
g[x].push_back(num);
}
cin >> x;
if(x == 0){
g[num].push_back(num+1);
g[num+1].push_back(num);
go(num+1);
} else {
g[num].push_back(x);
g[x].push_back(num);
}
}
void solve(){
cin >> n;
int a;
cin >> a;
go(n+1);
precalc(n+1,0);
dfs(n+1,0);
cout << ans[n+1] << "\n";
}
/*
*/
signed main(){
ios;
solve();
return 0;
}
Compilation message
rot.cpp: In function 'void dfs(int, int)':
rot.cpp:58:20: error: expected ';' before '}' token
58 | sort(all(vec[v]))
| ^
| ;
59 | }
| ~
