#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA
pii operator + (const pii &p1, const pii &p2) { return pii(p1.first + p2.first, p1.second + p2.second); }
struct SegTrees {
struct Node { int cnt = 0, lt = -1, rt = -1; };
vector<Node> seg;
deque<int> unused_id;
int maxn;
void init(int N) {
maxn = N + 1; // (1 << (__lg(N+1) + 1));
}
int new_node(int cnt = 0, int lt = -1, int rt = -1) {
if (SZ(unused_id)) {
int id = unused_id[0]; unused_id.pf();
seg[id] = Node{.cnt = cnt, .lt = lt, .rt = rt};
return id;
}
seg.eb(Node{.cnt = cnt, .lt = lt, .rt = rt});
return SZ(seg) - 1;
}
int create_tree(int qX) { return create_tree(qX, 0, maxn-1); }
int create_tree(int qX, int nL, int nR) {
// debug(qX, nL, nR);
if (nL == nR) return new_node(1);
int nM = (nL + nR) >> 1, lt = -1, rt = -1;
if (qX <= nM) lt = create_tree(qX, nL, nM);
if (nM < qX) rt = create_tree(qX, nM+1, nR);
return new_node(1, lt, rt);
}
pii merge(int L, int R) {
pii cost{
i64(~seg[L].rt ? seg[seg[L].rt].cnt : 0) * i64(~seg[R].lt ? seg[seg[R].lt].cnt : 0),
i64(~seg[L].lt ? seg[seg[L].lt].cnt : 0) * i64(~seg[R].rt ? seg[seg[R].rt].cnt : 0)
};
seg[L].cnt += seg[R].cnt;
if (~seg[L].lt and ~seg[R].lt) cost = cost + merge(seg[L].lt, seg[R].lt);
else chmax(seg[L].lt, seg[R].lt);
if (~seg[L].rt and ~seg[R].rt) cost = cost + merge(seg[L].rt, seg[R].rt);
else chmax(seg[L].rt, seg[R].rt);
unused_id.eb(R);
return cost;
}
int dfs(auto &ch, auto &ans, int now) {
if (ch[now].first == 0) return create_tree(now);
int lt = dfs(ch, ans, ch[now].first);
int rt = dfs(ch, ans, ch[now].second);
pii tmp = merge(lt, rt);
// debug(now, tmp);
ans[now] = ans[ch[now].first] + ans[ch[now].second] + min(tmp.first, tmp.second);
return lt;
}
};
void solve() {
int N; cin >> N;
vector<pii> ch(2*N, {0, 0});
int tok = 2*N;
function<int()> input = [&]() -> int {
int id; cin >> id;
if (id == 0) id = --tok, ch[id].first = input(), ch[id].second = input();
return id;
};
input();
// assert(tok == N+1);
vector<int> sz(2*N, 0);
fill_n(begin(sz) + 1, N, 1);
for (int i = N+1; i <= 2*N-1; ++i) {
if (sz[ch[i].first] < sz[ch[i].second]) swap(ch[i].first, ch[i].second);
sz[i] = sz[ch[i].first] + sz[ch[i].second];
}
// debug(ch, sz);
vector<i64> ans(2*N, 0);
SegTrees segs; segs.init(N);
segs.dfs(ch, ans, 2*N-1);
print(ans[2*N-1]);
// debug(ans);
}
int32_t main() {
fastIO();
int t = 1; // cin >> t;
for (int _ = 1; _ <= t; ++_) {
// cout << "Case #" << _ << ": ";
solve();
}
return 0;
}
#else
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
// using i128 = __int128;
// #define int i64
using f80 = long double;
// using f128 = __float128;
#define double f80
using pii = pair<i64, i64>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;
// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())
template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
static_assert(D >= 1, "Vector dimension must be greater than zero!");
template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {}
};
template <typename T> struct Vec<1, T> : vector<T> {
Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
};
template <class F>
inline constexpr decltype(auto) lambda_fix(F&& f) {
return [f = std::forward<F>(f)](auto&&... args) {
return f(f, std::forward<decltype(args)>(args)...);
};
}
#ifdef local
#define fastIO() void()
#define debug(...) \
_color.emplace_back("\u001b[31m"), \
fprintf(stderr, "%sAt [%s], line %d: (%s) = ", _color.back().c_str(), __FUNCTION__, __LINE__, #__VA_ARGS__), \
_do(__VA_ARGS__), _color.pop_back(), \
fprintf(stderr, "%s", _color.back().c_str())
#define print(...) \
fprintf(stdout, "%s", "\u001b[36m"), \
_P(__VA_ARGS__), \
fprintf(stdout, "%s", "\u001b[0m")
deque<string> _color{"\u001b[0m"};
template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>;
template <typename T> concept is_iterable = requires (T _t) {begin(_t);};
template <typename T> inline void _print_err(T &&_t);
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(tuple<U...> &_t);
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu);
inline void _do() {cerr << "\n";};
template <typename T> inline void _do(T &&_t) {_print_err(_t), cerr << "\n";}
template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) {_print_err(_t), cerr << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#endif
inline void _P() {cout << "\n";};
template <typename T> inline void _P(T &&_t) {cout << _t << "\n";}
template <typename T, typename ...U> inline void _P(T &&_t, U &&..._u) {cout << _t << " ", _P(_u...);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int getRand(int L, int R) {
if (L > R) swap(L, R);
return (int)(rng() % ((uint64_t)R - L + 1) + L);
}
template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}
/// below are Fast I/O and _print_err templates ///
/*
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
#include <unistd.h>
const int S = 65536;
int OP = 0;
char OB[S];
inline char RC() {
static char buf[S], *p = buf, *q = buf;
return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
}
inline int RI() {
static char c;
int a;
while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
if (c == '-') {
a = 0;
while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
}
else {
a = c ^ '0';
while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
}
return a;
}
inline void WI(int n, char c = '\n') {
static char buf[20], p;
if (n == 0) OB[OP++] = '0';
p = 0;
if (n < 0) {
OB[OP++] = '-';
while (n) buf[p++] = '0' - (n % 10), n /= 10;
}
else {
while (n) buf[p++] = '0' + (n % 10), n /= 10;
}
for (--p; p >= 0; --p) OB[OP++] = buf[p];
OB[OP++] = c;
if (OP > S-20) write(1, OB, OP), OP = 0;
}
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
*/
#ifdef local
template <typename T> inline void _print_err(T &&_t) {cerr << _t;}
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) {
string _tmp_color = _color.back();
++_tmp_color[3], _color.emplace_back(_tmp_color);
cerr << _color.back() << "[";
for (bool _first = true; auto &_x : _t) {
if (!_first) cerr << ", ";
_print_err(_x), _first = false;
}
cerr << "]" << (_color.pop_back(), _color.back());
}
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu) {
string _tmp_color = _color.back();
++_tmp_color[3], _color.emplace_back(_tmp_color);
cerr << _color.back() << "(";
_print_err(_tu.first), cerr << ", ", _print_err(_tu.second);
cerr << ")" << (_color.pop_back(), _color.back());
return os;
}
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &) {
cerr << ")" << (_color.pop_back(), _color.back());
}
template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t) {
if (!I) {
string _tmp_color = _color.back();
++_tmp_color[3], _color.emplace_back(_tmp_color);
cerr << _color.back();
}
cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) {
cerr << ")" << (_color.pop_back(), _color.back());
}
template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(tuple<U...> &_t) {
if (!I) {
string _tmp_color = _color.back();
++_tmp_color[3], _color.emplace_back(_tmp_color);
cerr << _color.back();
}
cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}
#endif
#endif
Compilation message
rot.cpp:57:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
57 | int dfs(auto &ch, auto &ans, int now) {
| ^~~~
rot.cpp:57:23: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
57 | int dfs(auto &ch, auto &ans, int now) {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
2 ms |
884 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1624 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
3052 KB |
Output is correct |
| 2 |
Correct |
7 ms |
2140 KB |
Output is correct |
| 3 |
Correct |
18 ms |
3804 KB |
Output is correct |
| 4 |
Correct |
7 ms |
3160 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
6856 KB |
Output is correct |
| 2 |
Correct |
23 ms |
7892 KB |
Output is correct |
| 3 |
Correct |
31 ms |
12824 KB |
Output is correct |
| 4 |
Correct |
29 ms |
11476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
20324 KB |
Output is correct |
| 2 |
Correct |
42 ms |
16076 KB |
Output is correct |
| 3 |
Correct |
54 ms |
11784 KB |
Output is correct |
| 4 |
Correct |
43 ms |
11464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
12456 KB |
Output is correct |
| 2 |
Correct |
66 ms |
13772 KB |
Output is correct |
| 3 |
Correct |
62 ms |
22728 KB |
Output is correct |
| 4 |
Correct |
60 ms |
22736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
24000 KB |
Output is correct |
| 2 |
Correct |
83 ms |
22340 KB |
Output is correct |
| 3 |
Correct |
98 ms |
21436 KB |
Output is correct |
| 4 |
Correct |
95 ms |
22160 KB |
Output is correct |
| 5 |
Correct |
113 ms |
24516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
22220 KB |
Output is correct |
| 2 |
Correct |
107 ms |
37824 KB |
Output is correct |
| 3 |
Correct |
122 ms |
29268 KB |
Output is correct |
| 4 |
Correct |
93 ms |
39356 KB |
Output is correct |
| 5 |
Correct |
124 ms |
27328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
27836 KB |
Output is correct |
| 2 |
Correct |
121 ms |
24768 KB |
Output is correct |
| 3 |
Correct |
124 ms |
20064 KB |
Output is correct |
| 4 |
Correct |
111 ms |
28092 KB |
Output is correct |
| 5 |
Correct |
117 ms |
35012 KB |
Output is correct |
| 6 |
Correct |
103 ms |
27328 KB |
Output is correct |
