#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int n0 = 2e5 + 123, inf = 1e8;
int n, used[n0], par[n0], k, c[n0], inc[n0], h[n0];
vector <int> g[n0];
void dfs(int v, int p) {
used[v] = 1;
for (int to : g[v]) {
if (to == p) continue;
if (used[to] == 1) {
int u = v;
while (u != to) {
c[++k] = u, inc[u] = 1;
u = par[u];
}
c[++k] = to, inc[to] = 1;
}
if (used[to] == 0) {
par[to] = v;
dfs(to, v);
}
}
used[v] = 2;
}
struct Pair {
int x, y;
Pair(int X = 0, int Y = 0) {
x = X, y = Y;
}
};
Pair max(const Pair & p1, const Pair & p2) {
if (p1.x > p2.x) return p1;
if (p2.x > p1.x) return p2;
return Pair(p1.x, p1.y + p2.y);
}
Pair b[n0], val[n0];
ll cnt[n0];
void go(int v, int p) {
b[v] = Pair(h[v], 1);
for (int to : g[v]) {
if (inc[to] || to == p) continue;
h[to] = h[v] + 1;
go(to, v);
b[v].x -= h[v];
val[to] = max(val[to], b[v]);
b[v].x += h[v];
b[v] = max(b[v], b[to]);
}
}
void go2(int v, int p) {
cnt[val[v].x + h[v]] += val[v].y;
for (int to : g[v]) {
if (inc[to] || to == p) continue;
val[to] = max(val[to], val[v]);
go2(to, v);
}
}
struct Node {
int l = 0, r = 0;
Pair x, y;
void clean() {
x.x = -inf, x.y = 0;
y.x = -inf, y.y = 0;
}
void init() {
x = Pair(b[c[l]].x + l, b[c[l]].y);
y = Pair(b[c[l]].x - l, b[c[l]].y);
}
void merge(const Node & L, const Node & R) {
x = max(L.x, R.x);
y = max(L.y, R.y);
}
};
Node t[(1 << 19) + 1];
void build(int v, int l, int r) {
t[v].l = l, t[v].r = r;
if (l == r) {
t[v].init();
return;
}
int m = l + r >> 1;
build(v << 1, l, m), build(v << 1 | 1, m + 1, r);
t[v].merge(t[v << 1], t[v << 1 | 1]);
}
Node res;
void get(int v, int l, int r) {
if (t[v].l > r || t[v].r < l) return;
if (t[v].l >= l && t[v].r <= r) {
res.merge(res, t[v]);
return;
}
get(v << 1, l, r), get(v << 1 | 1, l, r);
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
cin >> n;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
g[x].pb(y), g[y].pb(x);
}
dfs(1, 1);
for (int i = 1; i <= n; i++)
if (inc[i]) go(i, i);
for (int i = 1; i <= n; i++)
if (inc[i]) go2(i, i);
build(1, 1, k);
//cerr << "k " << k << '\n';
//for (int i = 1; i <= k; i++) {
//cerr << c[i] << ' ';
//}
//cerr << '\n';
//for (int i = 1; i <= k; i++) {
//cerr << b[c[i]].x << ' ' << b[c[i]].y;
//if (i < k) cerr << ", ";
//}
//cerr << '\n';
for (int i = 1; i <= k; i++) {
int l = i + 1, r = min(k, i + k / 2);
//cerr << "v " << c[i] << '\n';
if (l <= r) {
res.clean(), get(1, l, r);
//cerr << "l r " << l << ' ' << r << '\n';
//cerr << "d w " << b[c[i]].x - i + res.x.x << ' ' << (ll)res.x.y * b[c[i]].y << '\n';
cnt[b[c[i]].x - i + res.x.x] += (ll)res.x.y * b[c[i]].y;
}
l = i + k / 2 + 1, r = k;
if (l <= r) {
res.clean(), get(1, l, r);
//cerr << "l r " << l << ' ' << r << '\n';
//cerr << "d w " << k + b[c[i]].x + i + res.y.x << ' ' << (ll)res.y.y * b[c[i]].y << '\n';
cnt[k + b[c[i]].x + i + res.y.x] += (ll)res.y.y * b[c[i]].y;
}
}
if (k % 2 == 0)
for (int i = 1; i + k / 2 <= k; i++)
cnt[k / 2 + b[c[i]].x + b[c[i + k / 2]].x] += (ll)b[c[i]].y * b[c[i + k / 2]].y;
for (int i = n; i > 0; i--)
if (cnt[i]) return cout << cnt[i], 0;
}
Compilation message
shymbulak.cpp: In function 'void build(int, int, int)':
shymbulak.cpp:99:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
20480 KB |
Output is correct |
| 2 |
Correct |
11 ms |
20480 KB |
Output is correct |
| 3 |
Correct |
12 ms |
20480 KB |
Output is correct |
| 4 |
Correct |
11 ms |
20480 KB |
Output is correct |
| 5 |
Correct |
11 ms |
20480 KB |
Output is correct |
| 6 |
Correct |
12 ms |
20480 KB |
Output is correct |
| 7 |
Correct |
11 ms |
20480 KB |
Output is correct |
| 8 |
Correct |
11 ms |
20480 KB |
Output is correct |
| 9 |
Correct |
11 ms |
20480 KB |
Output is correct |
| 10 |
Incorrect |
12 ms |
20480 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
20608 KB |
Output is correct |
| 2 |
Correct |
12 ms |
20608 KB |
Output is correct |
| 3 |
Correct |
12 ms |
20608 KB |
Output is correct |
| 4 |
Correct |
12 ms |
20608 KB |
Output is correct |
| 5 |
Correct |
14 ms |
20736 KB |
Output is correct |
| 6 |
Correct |
13 ms |
20864 KB |
Output is correct |
| 7 |
Correct |
15 ms |
20736 KB |
Output is correct |
| 8 |
Incorrect |
14 ms |
20736 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
25464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
