#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 200001;
int N, p[MX];
vi adj[MX];
bitset<MX> vis, incyc;
pi des = {-1,-1};
pl ans = {0,0};
vi cyc;
void ad(int x, ll y) {
if (ans.f < x) ans = {x,0};
if (ans.f == x) ans.s += y;
}
void dfs(int a, int b = 0) {
p[a] = b; vis[a] = 1;
for (int i: adj[a]) if (i != p[a]) {
if (vis[i]) {
des = {a,i};
break;
}
dfs(i,a);
if (des != mp(-1,-1)) break;
}
}
void init() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
F0R(i,N) {
/*int a,b; // int a = i+1,b = (i+1)%N+1;
if (i == 0) {
a = N;
b = rand() % (N-1)+1;
} else {
a = i+1;
b = rand() % i +1;
}*/
int a,b; cin >> a >> b;
adj[a].pb(b), adj[b].pb(a);
}
dfs(1);
while (des.f != des.s) cyc.pb(des.f), des.f = p[des.f];
cyc.pb(des.s);
for (int i: cyc) incyc[i] = 1;
}
pi dfs2(int a, int b = 0) {
vpi v;
for (int i: adj[a]) if (i != b && !incyc[i]) {
auto A = dfs2(i,a); A.f ++;
v.pb(A);
}
v.pb({0,1});
sort(all(v)); reverse(all(v));
int ind = 0, tot = 0;
while (ind < sz(v) && v[ind].f == v[0].f) tot += v[ind++].s;
if (ind == 1) {
int ind2 = 1;
ll tot2 = 0;
while (ind2 < sz(v) && v[ind2].f == v[1].f) tot2 += v[ind2++].s;
if (sz(v) > 1) ad(v[0].f+v[1].f,(ll)tot2*tot);
} else {
ll TOT = (ll)tot*(tot-1)/2;
F0R(i,ind) TOT -= (ll)v[i].s*(v[i].s-1)/2;
ad(2*v[0].f,TOT);
}
return {v[0].f,tot};
}
vpi CYC;
int getSum(int x) {
return CYC[x%sz(cyc)].s;
}
pi csum = {MOD,0};
deque<pi> d;
void pb(pi x) {
d.pb(x);
if (csum.f == MOD) csum.f = x.f;
if (csum.f == x.f) csum.s += getSum(x.s);
}
void pop_back() {
if (d.back().f == csum.f) {
csum.s -= getSum(d.back().s);
if (csum.s == 0) csum = {MOD,0};
}
d.pop_back();
}
void pop_front() {
if (d.front().f == csum.f) {
csum.s -= getSum(d.front().s);
if (csum.s == 0) csum = {MOD,0};
}
d.pop_front();
}
void ins(int x) {
pi des = {CYC[x%sz(cyc)].f-x,x};
while (sz(d) && d.back().f < des.f) pop_back();
pb(des);
}
void del(int x) {
while (d.front().s < x) {
pop_front();
if (csum.f == MOD) {
csum = {d.front().f,0};
stack<pi> tmp;
while (sz(d) && d.front().f == csum.f) {
csum.s += getSum(d.front().s);
tmp.push(d.front()); d.pop_front();
}
while (sz(tmp)) {
d.push_front(tmp.top());
tmp.pop();
}
}
}
}
int main() {
init();
for (int i: cyc) CYC.pb(dfs2(i));
int t = sz(cyc)/2;
F0R(i,2*sz(cyc)) {
if (i >= t && i < sz(cyc)+t) {
del(i-t);
//cout << "OH " << sz(d) << " " << d.front().s << "\n";
//cout << cyc[i%sz(cyc)] << " " << csum.f << " " << i << " " << getSum(i) << "\n";
ad(csum.f+i+CYC[i%sz(cyc)].f,(ll)csum.s*getSum(i));
}
ins(i);
}
cout << ans.s;
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5232 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5332 KB |
Output is correct |
| 4 |
Correct |
9 ms |
5332 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5496 KB |
Output is correct |
| 6 |
Correct |
6 ms |
5496 KB |
Output is correct |
| 7 |
Correct |
7 ms |
5496 KB |
Output is correct |
| 8 |
Correct |
7 ms |
5496 KB |
Output is correct |
| 9 |
Correct |
6 ms |
5496 KB |
Output is correct |
| 10 |
Correct |
8 ms |
5496 KB |
Output is correct |
| 11 |
Correct |
8 ms |
5504 KB |
Output is correct |
| 12 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 13 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 14 |
Correct |
6 ms |
5516 KB |
Output is correct |
| 15 |
Correct |
6 ms |
5516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5524 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5536 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5560 KB |
Output is correct |
| 4 |
Correct |
10 ms |
5708 KB |
Output is correct |
| 5 |
Correct |
12 ms |
5708 KB |
Output is correct |
| 6 |
Correct |
9 ms |
5908 KB |
Output is correct |
| 7 |
Correct |
13 ms |
5908 KB |
Output is correct |
| 8 |
Correct |
12 ms |
5924 KB |
Output is correct |
| 9 |
Correct |
12 ms |
5928 KB |
Output is correct |
| 10 |
Correct |
10 ms |
5976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
10248 KB |
Output is correct |
| 2 |
Correct |
133 ms |
11852 KB |
Output is correct |
| 3 |
Correct |
85 ms |
16068 KB |
Output is correct |
| 4 |
Correct |
81 ms |
16068 KB |
Output is correct |
| 5 |
Correct |
100 ms |
16068 KB |
Output is correct |
| 6 |
Correct |
268 ms |
20308 KB |
Output is correct |
| 7 |
Correct |
199 ms |
21060 KB |
Output is correct |
| 8 |
Correct |
158 ms |
25020 KB |
Output is correct |
| 9 |
Correct |
118 ms |
27384 KB |
Output is correct |
| 10 |
Correct |
139 ms |
30936 KB |
Output is correct |
| 11 |
Correct |
144 ms |
34992 KB |
Output is correct |
| 12 |
Correct |
216 ms |
37876 KB |
Output is correct |
