#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; 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.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};
}
deque<pair<pi,queue<int>>> d;
vpi CYC;
void ins(int x) {
pi des = {CYC[x%sz(cyc)].f-x,CYC[x%sz(cyc)].s};
while (sz(d) && d.back().f.f < des.f) d.pop_back();
if (!sz(d) || d.back().f.f > des.f) d.pb({{des.f,0},queue<int>()});
d.back().s.push(x);
d.back().f.s += des.s;
}
void del(int x) {
while (1) {
if (!sz(d.front().s)) d.pop_front();
else {
int t = d.front().s.front();
if (t < x) {
d.front().f.s -= CYC[t%sz(cyc)].s;
d.front().s.pop();
} else break;
}
}
}
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 " << cyc[i%sz(cyc)] << " " << CYC[i%sz(cyc)].f << " " << d.front().f.f << " " << CYC[i%sz(cyc)].f << " " << i << "\n";
ad(d.front().f.f+i+CYC[i%sz(cyc)].f,(ll)d.front().f.s*CYC[i%sz(cyc)].s);
// cout << "OOPS " << (ll)d.front().f.s << " " << CYC[i%sz(cyc)].s << "\n";
// cout << "AH " << ans.f << " " << ans.s << "\n";
}
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 |
7 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5224 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5248 KB |
Output is correct |
| 4 |
Runtime error |
825 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
936 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
