#include <bits/stdc++.h>
#define fr first
#define pb push_back
#define sc second
#define ll long long
using namespace std;
const int N = 2e5 + 7;
const int inf = 1e9 + 7;
vector<int>g[N];
int c[N];
set<int, greater<int>>st1;
set<int, greater<int>>st2;
map<int, ll>mp1;
map<int, ll>mp2;
map<ll, ll>cnt;
int qt[N], tin[N], cn, fup[N];
ll mx = -1;
map<pair<int, int>, bool>is_b;
bool us[N];
int ver;
int cycn;
void dfs(int v, int p)
{
tin[v] = fup[v] = ++cn;
us[v] = 1;
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (to == p)continue;
if (us[to])
{
fup[v] = min(fup[v], tin[to]);
}
else
{
dfs(to, v);
fup[v] = min(fup[v], fup[to]);
if (fup[to] > tin[v])
is_b[{v, to}] = 1, is_b[{to, v}] = 1;
else
ver = to;
}
}
}
pair<int, int> deep(int v, int p)
{
ll mxx = -1, mx1 = -1;
ll eq = 1, eq1 = 1;
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (to == p || !is_b[{v, to}])continue;
pair<ll, ll> q = deep(to, v);
if (mxx < q.fr)
{
if (mx1 != mxx)
eq1 = eq;
mx1 = mxx;
mxx = q.fr;
eq = q.sc;
}
else
{
if (q.fr == mxx)
eq += q.sc;
if (q.fr == mx1)
eq1 += q.sc;
if (q.fr > mx1)
eq1 = q.sc;
mx1 = max(mx1, q.fr * 1LL);
}
}
mxx++; mx1++;
ll col = eq * 1LL * eq1;
if (mxx == mx1)
col = (eq * (eq - 1)) / 2;
mx = max(mxx + mx1, mx);
cnt[mxx + mx1] += col;
return {mxx, eq};
}
void dfs1(int v, int p, int id)
{
us[v] = 1;
cycn++;
us[v] = 1;
int mx = 0;
int cnt = 0;
pair<int, int>q = deep(v, p);
mx = q.fr, cnt = q.sc;
c[id] = mx;
qt[id] = cnt;
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (us[to] || is_b[{v, to}])continue;
dfs1(to, v, id + 1);
}
}
void dfs2(int v, int p, int id)
{
us[v] = 1;
if (id != 0)
{
ll len = (*st1.begin()) + id + c[id];
mx = max(mx, len);
cnt[len] += (mp1[len - id - c[id]] * 1LL * qt[id]);
if (st2.size())
{
len = (*st2.begin()) - id + c[id];
mx = max(mx, len);
cnt[len] += (mp2[len + id - c[id]] * 1LL * qt[id]);
}
}
st1.insert(c[id] - id);
mp1[c[id] - id] += qt[id];
int prev = cycn / 2;
if (id >= prev)
{
mp1[c[id - prev] - id + prev] -= qt[id - prev];
if (mp1[c[id - prev] - id + prev] == 0)
st1.erase(c[id - prev] - id + prev);
st2.insert(c[id - prev] + cycn + id - prev);
mp2[c[id - prev] + cycn + id - prev] += qt[id - prev];
}
if (cycn % 2 == 0 && id >= prev - 1)
{
st2.insert(cycn + (id - prev + 1) + c[id - prev + 1]);
mp2[cycn + (id - prev + 1) + c[id - prev + 1]] += qt[id - prev + 1];
}
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (is_b[{v, to}] || us[to])continue;
dfs2(to, v, id + 1);
}
}
main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
g[a].pb(b);
g[b].pb(a);
}
dfs(1, 0);
memset(us, 0, sizeof(us));
dfs1(ver, 0, 0);
memset(us, 0, sizeof(us));
dfs2(ver, 0, 0);
//cout << mx << endl;
cout << cnt[mx] << endl;
}
/*
* Find Bridges
* Assign c[i]s (length of subtree) and q[i] number of them and cyc -> length of cycle
* Dance
*/
/*
6
1 2
1 3
2 3
3 4
4 6
3 5
*/
Compilation message
shymbulak.cpp: In function 'void dfs(int, int)':
shymbulak.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'std::pair<int, int> deep(int, int)':
shymbulak.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs1(int, int, int)':
shymbulak.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs2(int, int, int)':
shymbulak.cpp:134:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
shymbulak.cpp: At global scope:
shymbulak.cpp:141:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5240 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5240 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5320 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5340 KB |
Output is correct |
| 5 |
Incorrect |
6 ms |
5424 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5932 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5932 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5932 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
5932 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
262 ms |
22148 KB |
Output is correct |
| 2 |
Incorrect |
267 ms |
23348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
