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 pb emplace_back
#define ll long long
const int N = 2e5+5, sizeBit = 2e5+5;
int ft[sizeBit];
int get(int p) {
int tot = 0;
for (; p <= N; p += p & -p)
tot += ft[p];
return tot;
}
void upd(int p, int v) {
for (; p; p -= p & -p)
ft[p] += v;
}
int n, a[N], curr = 1, sz[N], big[N];
vector<int> g[N];
ll ans[N], inv;
void read() {
int x;
cin >> x;
if (x) return a[curr] = x, void();
int tmp = curr;
g[tmp].pb(++curr); g[curr].pb(tmp);
read(); // cay con trai
g[tmp].pb(++curr); g[curr].pb(tmp);
read(); // cay con phai
}
void dfs_sz(int u, int pre = -1) {
sz[u] = (a[u] > 0); big[u] = 0;
for (int v : g[u]) if (v != pre) {
dfs_sz(v, u);
sz[u] += sz[v];
if (sz[v] > sz[big[u]]) big[u] = v;
}
}
void add_inv(int u, int pre) {
if (a[u]) {
inv += get(a[u]+1);
return;
}
for (int v : g[u]) if (v != pre)
add_inv(v, u);
}
void add_bit(int u, int pre) {
if (a[u]) {
upd(a[u], 1);
return;
}
for (int v : g[u]) if (v != pre)
add_bit(v, u);
}
void del(int u, int pre) {
if (a[u]) {
upd(a[u], -1);
return;
}
for (int v : g[u]) if (v != pre)
del(v, u);
}
void add(int u, int pre) {
add_inv(u, pre);
add_bit(u, pre);
}
void dfs(int u, int pre) {
if (a[u]) {
add(u, pre);
return;
}
int node;
for (int v : g[u]) if (v != pre && v != big[u]) {
dfs(v, u);
ans[u] += ans[v];
del(v, u);
node = v;
}
dfs(big[u], u);
ans[u] += ans[big[u]];
inv = 0; add(node, u);
ans[u] += min(inv, 1LL * sz[big[u]] * sz[node] - inv);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n; read();
dfs_sz(1, 1); dfs(1, 1);
cout << ans[1];
}
Compilation message (stderr)
rot.cpp: In function 'void dfs(int, int)':
rot.cpp:92:48: warning: 'node' may be used uninitialized in this function [-Wmaybe-uninitialized]
92 | ans[u] += min(inv, 1LL * sz[big[u]] * sz[node] - inv);
| ~~~~~~~^
# | 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... |