#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;
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];
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] = max(b[v], b[to]);
}
}
struct Node {
int l = 0, r = 0;
Pair x, y;
void clean() {
x.x = -n0, x.y = 0;
y.x = -n0, 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];
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);
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 + k / 2 + 1, r = k;
//cerr << "i " << i << '\n';
if (l <= r) {
//cerr << "l r " << l << ' ' << r << '\n';
res.clean(), get(1, l, r);
if (res.x.x != -n0) {
//cerr << "d " << res.x.x + (k + b[c[i]].x + i) << ' ' << (ll)2 * res.x.y * b[c[i]].y << '\n';
cnt[res.x.x + (k + b[c[i]].x + i)] += (ll)2 * res.x.y * b[c[i]].y;
}
}
l = i + 1, r = min(k, i + k / 2);
if (l <= r) {
//cerr << "l r " << l << ' ' << r << '\n';
res.clean(), get(1, l, r);
if (res.y.x != -n0) {
//cerr << "d " << res.y.x + (b[c[i]].x - i) << ' ' << (ll)2 * res.y.y * b[c[i]].y << '\n';
//cerr << "res " << res.y.x << ' ' << res.y.y << '\n';
cnt[res.y.x + (b[c[i]].x - i)] += (ll)2 * res.y.y * b[c[i]].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:87:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
18944 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
18944 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
19072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
65 ms |
23416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
