This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
const ll N = 2e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 450;
ll n, m, res = 0;
ll a[N], sz[N], heavy[N];
vector<ll>adj[N];
set<ll>s[N];
struct fenwick_tree{
ll n;
vector<ll>ft;
void init(ll _n){
n = _n;
ft.resize(n + 10);
}
void update(ll idx, ll val){
while(idx <= n){
ft[idx] += val;
idx += (idx & (-idx));
}
}
ll get(ll idx){
ll res = 0;
while(idx > 0){
res += ft[idx];
idx -= (idx & (-idx));
}
return res;
}
} ft;
ll idx = 1;
void input(){
ll x; cin >> x;
a[idx] = x;
if(x != 0) return;
ll cur = idx;
idx++;
adj[cur].pb(idx);
input();
idx++;
adj[cur].pb(idx);
input();
}
void pre_dfs(ll u, ll par){
sz[u] = 1;
for(auto v : adj[u]){
if(v == par) continue;
pre_dfs(v, u);
sz[u] += sz[v];
if(sz[v] > sz[heavy[u]]) heavy[u] = v;
}
}
void change(ll u, ll par, ll val){
if(a[u] > 0) ft.update(a[u], val);
for(auto v : adj[u]){
if(v != par) change(v, u, val);
}
}
void dfs(ll u, ll par){
if(a[u] != 0){
s[u].insert(a[u]);
ft.update(a[u], 1);
return;
}
for(auto v : adj[u]){
if(v != heavy[u] && v != par){
dfs(v, u);
change(v, u, -1);
if(s[u].size() < s[v].size()) swap(s[u], s[v]);
for(auto x : s[v]) s[u].insert(x);
}
}
dfs(heavy[u], u);
ll inv = 0;
for(auto x : s[u]){
inv = (inv + ft.get(x - 1));
}
if(s[heavy[u]].size() > s[u].size()) swap(s[heavy[u]], s[u]);
for(auto x : s[heavy[u]]) s[u].insert(x);
for(auto v : adj[u]){
if(v != par && v != heavy[u]) change(v, u, 1);
}
ll cur_sz = s[u].size();
res += min(cur_sz * (cur_sz - 1) / 2 - inv, inv);
}
void to_thic_cau(){
ll n; cin >> n;
input();
ft.init(idx);
pre_dfs(1, 0);
for(int i = 1; i <= idx;i++) {
sort(all(adj[i]), [&](const ll &a, const ll &b){
return sz[a] < sz[b];
});
}
dfs(1, 0);
cout << res << '\n';
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll tc = 1;
//cin >> tc;
while(tc--) to_thic_cau();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |