//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 <ll, ll>
#define sz(a) (ll)(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;
ll n, a, b, sz;
map <pii, ll> M;
ll vis[N], L[N*4];
pii p[N], H[N][5], S[N*4];
vector <ll> E[N], arr, v, T[N];
void dfs(ll nd, ll pr)
{
arr.pb(nd);
vis[nd] = vis[pr]+1;
for(auto i: E[nd]) {
if(i == pr) continue;
if(vis[i]) {
for(ll 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(ll 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};
if(H[nd][0].ff == H[i][0].ff) H[nd][0].ss += H[i][0].ss;
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;
}
}
H[nd][0] = {H[nd][0].ff+1, max(1LL, H[nd][0].ss)};
H[nd][1] = {H[nd][1].ff+1, max(1LL, H[nd][1].ss)};
}
void com(ll 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(ll l, ll r, ll 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(ll node, ll to)
{
L[to] += L[node];
S[to].ff += L[node];
}
void upd(ll a, ll b, ll x, ll l, ll r, ll 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(ll pos, double x, ll l, ll r, ll 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(ll pos, pii x, ll l, ll r, ll 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(ll l, ll r, ll 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(ll 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(ll i = 1; i < v.size(); i++) M[{v[i], v[i-1]}] = M[{v[i-1], v[i]}] = 1;
for(ll 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(ll i = 1; i <= sz; i++) p[i] = H[v[i-1]][0];
for(ll 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);
ll l = 2, lm = (sz-1)/2, pos = -1, last = -1, mx = 0, ans = 0;
if(sz%2 == 0) pos = sz/2+1;
for(ll 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);
ll now = S[1].ff + H[v[i-1]][0].ff - 1;
ll 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) {
ll 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
4
1 2
1 3
1 4
4 3
------------------------- 2
9
1 2
1 3
2 3
3 4
4 5
5 6
3 7
7 8
8 9
------------------------ 1
8
1 2
3 4
5 6
7 8
2 4
4 7
7 5
5 2
----------------------- 4
7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
---------------------- 7
12
1 3
2 3
7 4
8 4
9 5
10 5
12 6
11 6
3 4
4 5
5 6
6 3
--------------------- 16
*/
Compilation message
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:186:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
186 | for(ll i = 1; i < v.size(); i++) M[{v[i], v[i-1]}] = M[{v[i-1], v[i]}] = 1;
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11392 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
11372 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
11628 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
11500 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
217 ms |
34148 KB |
Output is correct |
| 2 |
Incorrect |
228 ms |
35064 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
