//Suleyman Atayew
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define N 200010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define mod 1000000007
#define pii pair <int, int>
#define sz(a) (int)(a.size())
ll bigmod(ll a, ll b) { if(b==0)return 1; ll ret = bigmod(a, b/2); return ret * ret % mod * (b%2 ? a : 1) % mod; }
using namespace std;
int n, a, b, sz;
map <pii, int> M;
int vis[N], L[N*4];
pii p[N], H[N][5], S[N*4];
vector <int> E[N], arr, v, T[N];
void dfs(int nd, int pr)
{
arr.pb(nd);
vis[nd] = vis[pr]+1;
for(auto i: E[nd]) {
if(i == pr) continue;
if(vis[i]) {
for(int h = vis[i]-1; h < vis[nd]; h++) v.pb(arr[h]);
return;
}
dfs(i, nd);
if(!v.empty()) return;
}
arr.pop_back();
vis[nd] = 0;
}
void dfs2(int nd)
{
vis[nd] = 1;
for(auto i: T[nd]) {
if(vis[i]) continue;
dfs2(i);
if(H[nd][0].ff < H[i][0].ff) H[nd][1] = H[nd][0], H[nd][0] = {H[i][0].ff, 0};
else {
if(H[nd][1].ff < H[i][0].ff) H[nd][1] = {H[i][0].ff, 0};
if(H[nd][1].ff == H[i][0].ff) H[nd][1].ss += H[i][0].ss;
}
if(H[nd][0].ff == H[i][0].ff) H[nd][0].ss += H[i][0].ss;
}
H[nd][0] = {H[nd][0].ff+1, max(1, H[nd][0].ss)};
H[nd][1] = {H[nd][1].ff+1, max(1, H[nd][1].ss)};
}
void com(int node) {
if(S[node*2].ff < S[node*2+1].ff) S[node] = S[node*2+1];
if(S[node*2].ff > S[node*2+1].ff) S[node] = S[node*2];
if(S[node*2].ff == S[node*2+1].ff) S[node] = {S[node*2].ff, S[node*2].ss + S[node*2+1].ss};
}
void build(int l, int r, int node)
{
if(l == r) {
S[node] = p[l];
return;
}
build(l, (l+r)/2, node*2);
build((l+r)/2+1, r, node*2+1);
com(node);
}
void shift(int node, int to)
{
L[to] += L[node];
S[to].ff += L[node];
}
void upd(int a, int b, int x, int l, int r, int node)
{
if(l > b || r < a) return;
if(l >= a && r <= b) {
S[node].ff += x;
L[node] += x;
return;
}
shift(node, node*2);
shift(node, node*2+1);
L[node] = 0;
upd(a, b, x, l, (l+r)/2, node*2);
upd(a, b, x, (l+r)/2+1, r, node*2+1);
com(node);
}
void upd2(int pos, double x, int l, int r, int node)
{
if(l == r) {
S[node].ss *= x;
return;
}
shift(node, node*2);
shift(node, node*2+1);
L[node] = 0;
if(pos <= (l+r)/2)
upd2(pos, x, l, (l+r)/2, node*2);
else
upd2(pos, x, (l+r)/2+1, r, node*2+1);
com(node);
}
pii upd3(int pos, pii x, int l, int r, int node)
{
if(l == r) {
pii a = S[node];
S[node] = x;
return a;
}
shift(node, node*2);
shift(node, node*2+1);
L[node] = 0;
pii ret;
if(pos <= (l+r)/2)
ret = upd3(pos, x, l, (l+r)/2, node*2);
else
ret = upd3(pos, x, (l+r)/2+1, r, node*2+1);
com(node);
return ret;
}
void job(int l, int r, int x)
{
if(r > sz) r -= sz;
if(l > sz) l -= sz;
if(r >= l) upd(l, r, x, 1, sz, 1);
else {
upd(l, sz, x, 1, sz, 1);
upd(1, r, x, 1, sz, 1);
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a >> b;
E[a].pb(b);
E[b].pb(a);
p[i] = {a, b};
}
dfs(1, 0);
sz = v.size();
M[{v[0], v.back()}] = M[{v.back(), v[0]}] = 1;
for(int i = 1; i < v.size(); i++) M[{v[i], v[i-1]}] = M[{v[i-1], v[i]}] = 1;
for(int i = 1; i <= n; i++) {
if(M[p[i]]) continue;
T[p[i].ff].pb(p[i].ss);
T[p[i].ss].pb(p[i].ff);
}
memset(vis, 0, sizeof(vis));
for(auto i: v) dfs2(i);
for(int i = 1; i <= sz; i++) p[i] = H[v[i-1]][0];
for(int i = 2, h = sz; i < h; i++, h--) p[i].ff += i-1, p[h].ff += i-1;
if(sz%2 == 0) p[sz/2+1].ff += sz/2;
build(1, sz, 1);
int l = 2, lm = (sz-1)/2, pos = -1, last = -1, mx = 0, ans = 0;
if(sz%2 == 0) pos = sz/2+1;
for(int i = 1; i <= sz; i++) {
pii cur = upd3(i, {0, 0}, 1, sz, 1);
if(last != -1) upd2(last, 0.5, 1, sz, 1);
if(pos != -1) upd2(pos, 2, 1, sz, 1);
int now = S[1].ff + H[v[i-1]][0].ff - 1;
int cnt = S[1].ss * H[v[i-1]][0].ss;
if(mx < now) {
mx = now;
ans = 0;
}
if(mx == now) ans += cnt;
upd3(i, cur, 1, sz, 1);
job(l, l+lm, -1);
job(sz-lm+i, i, 1);
l++;
if(pos == -1) continue;
last = pos, pos++;
if(pos > sz) pos -= sz;
}
for(auto i: v) {
int now = 0, cnt = 2, ok = 0;
for(auto h: T[i])
if(H[h][0].ff == H[i][0].ff - 1) {
ok ++;
cnt *= H[h][0].ss;
}
if(ok <= 1) {
now = H[i][1].ff + H[i][0].ff - 1;
cnt = H[i][1].ss * H[i][0].ss * 2;
} else {
now = H[i][0].ff * 2 - 1;
}
if(mx < now) {
mx = now;
ans = 0;
}
if(mx == now) ans += cnt;
}
cout << ans/2;
}
/*
6
1 2
1 3
2 4
4 3
4 5
4 6
4
1 2
1 3
1 4
4 3
9
1 2
1 3
2 3
3 4
4 5
5 6
3 7
7 8
8 9
8
1 2
3 4
5 6
7 8
2 4
4 7
7 5
5 2
*/
Compilation message
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:187:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
187 | for(int i = 1; i < v.size(); i++) M[{v[i], v[i-1]}] = M[{v[i-1], v[i]}] = 1;
| ~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
10476 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
10476 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
10732 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
10732 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
226 ms |
26980 KB |
Output is correct |
| 2 |
Incorrect |
213 ms |
28260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
