#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define pll pair<ll, ll>
using namespace std;
typedef long long ll;
const ll OO = 1e18;
const int N = 200100;
const int M = 1010;
const int big = 1e8;
//const int PW = (1 << N);
vector<int> vc, g[N], cyc;
int mrk[N], n, mx1[N], mx2[N], kl1[N], kl2[N], ans = -1, m, mm, pos[N];
ll st[4 * N], psh[4 * N];
ll kans = 0, kol[4 * N];
bool in_cyc[N];
void CYCLE(int lst){
cyc.clear();
int it = sz(vc) - 1;
while (1){
cyc.PB(vc[it]);
in_cyc[vc[it]] = 1;
if (vc[it] == lst)
break;
it--;
}
}
void dfs(int v, int p){
if (sz(cyc) > 0) return;
vc.PB(v);
mrk[v] = 1;
for (int u : g[v]){
if (u == p) continue;
if (mrk[u] == 0)
dfs(u, v); else
if (mrk[u] == 1)
CYCLE(u);
}
mrk[v] = 2;
vc.pop_back();
}
void calc_max(int v, int p){
mx1[v] = 0; mx2[v] = -1;
kl1[v] = 1; kl2[v] = 0;
int ko = 1;
ll res = 0, sm = 0;
for (int u : g[v]){
if (u == p || in_cyc[u]) continue;
calc_max(u, v);
if (mx1[v] == mx1[u] + 1){
kl1[v] += kl1[u];
ko++;
res += sm * ll(kl1[u]);
sm += kl1[u];
} else if (mx1[v] < mx1[u] + 1){
swap(kl1[v], kl2[v]);
swap(mx1[v], mx2[v]);
kl1[v] = kl1[u];
ko = 1;
res = 0;
sm = kl1[u];
mx1[v] = mx1[u] + 1;
} else if (mx2[v] == mx1[u] + 1){
kl2[v] += kl1[u];
} else if (mx2[v] < mx1[u] + 1) {
kl2[v] = kl1[u];
mx2[v] = mx1[u] + 1;
}
}
if (mx1[v] < 1) return;
if (ko > 1){
if (mx1[v] + mx1[v] > ans){
ans = mx1[v] + mx1[v];
kans = 0;
}
if (mx1[v] + mx1[v] == ans)
kans += res * 2;
} else {
if (mx1[v] + mx2[v] > ans){
ans = mx1[v] + mx2[v];
kans = 0;
}
if (mx1[v] + mx2[v] == ans)
kans += ll(kl1[v]) * ll(kl2[v]) * 2;
}
}
void build(int v, int l, int r){
psh[v] = 0;
if (l == r){
st[v] = mx1[cyc[l]] + min(l, m - l);
kol[v] = kl1[cyc[l]];
return;
}
int md = (l + r) >> 1;
build(v + v, l, md);
build(v + v + 1, md + 1, r);
st[v] = max(st[v + v], st[v + v + 1]);
kol[v] = 0;
if (st[v] == st[v + v])
kol[v] += kol[v + v];
if (st[v] == st[v + v + 1])
kol[v] += kol[v + v + 1];
}
void push(int v){
if (psh[v] != 0){
st[v] += psh[v];
if (v + v + 1 < 4 * n){
psh[v + v] += psh[v];
psh[v + v + 1] += psh[v];
}
psh[v] = 0;
}
}
void update(int v, int tl, int tr, int l, int r, int vl){
if (l > r) return;
push(v);
if (tl == l && tr == r){
psh[v] += vl;
push(v);
return;
}
int md = (tl + tr) >> 1;
update(v + v, tl, md, l, min(r, md), vl);
update(v + v + 1, md + 1, tr, max(l, md + 1), r, vl);
st[v] = max(st[v + v], st[v + v + 1]);
kol[v] = 0;
if (st[v] == st[v + v])
kol[v] += kol[v + v];
if (st[v] == st[v + v + 1])
kol[v] += kol[v + v + 1];
}
void upd(int l, int r, int vl){
if (l < 0){
update(1, 0, m - 1, 0, r, vl);
update(1, 0, m - 1, m + l, m - 1, vl);
} else if (r >= m){
update(1, 0, m - 1, l, m - 1, vl);
update(1, 0, m - 1, 0, r - m, vl);
} else {
update(1, 0, m - 1, l, r, vl);
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("penguins.in","r",stdin); freopen("penguins.out","w",stdout);
// freopen("in.txt","r",stdin);
cin >> n;
for (int i = 0; i < n; i++){
int x, y;
cin >> x >> y;
x--; y--;
g[x].PB(y);
g[y].PB(x);
}
dfs(0, -1);
for (int it = 0; it < sz(cyc); it++){
int cr = cyc[it];
pos[cr] = it;
calc_max(cr, -1);
}
bool good = (sz(cyc) % 2 == 0);
m = sz(cyc);
mm = m / 2;
build(1, 0, m - 1);
for (int it = 0; it < m; it++){
int v = cyc[it];
if (it > 0){
upd(it - mm, it - 1, +1);
upd(it, it + mm - 1, -1);
}
update(1, 0, m - 1, it, it, -big);
ll mdst = st[1] + mx1[v];
if (mdst > ans){
ans = mdst;
kans = 0;
}
if (mdst == ans)
kans += ll(kl1[v]) * kol[1];
if (good){
int op = cyc[(it + mm) % m];
if (mm + mx1[op] + mx1[v] == ans)
kans += ll(kl1[op]) * ll(kl1[v]);
}
update(1, 0, m - 1, it, it, +big);
}
// for (int i1 = 0; i1 < sz(cyc); i1++)
// for (int i2 = i1 + 1; i2 < sz(cyc); i2++){
// int dst = i2 - i1, n1 = cyc[i1], n2 = cyc[i2];
// dst = min(dst, sz(cyc) - dst);
// dst += mx1[n1] + mx1[n2];
//
// if (dst > ans){
// ans = dst;
// kans = 0;
// }
//
// if (dst == ans)
// kans += ll(kl1[n1]) * ll(kl1[n2]);
//
// if (good && (i2 - i1) == (sz(cyc) >> 1) && dst == ans)
// kans += ll(kl1[n1]) * ll(kl1[n2]);
// }
cout << kans / 2 << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5112 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
5112 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
10332 KB |
Output is correct |
| 2 |
Correct |
89 ms |
10864 KB |
Output is correct |
| 3 |
Incorrect |
137 ms |
18164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
