#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;
}
}
}
int deep(int v, int p, int &cnt, int x, int c = 1)
{
int mx = c;
if (c == x)
{
cnt++;
}
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (to == p)continue;
mx = max(mx, deep(to, v, cnt, x, c + 1));
}
return mx;
}
void dfs1(int v, int p, int id)
{
us[v] = 1;
cycn++;
us[v] = 1;
int mx = 0, trash = 0;
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (!is_b[{v, to}])continue;
mx = max(mx, deep(to, v, trash, 0));
}
int cnt = 0;
bool fl = 0;
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (!is_b[{v, to}])continue;
deep(to, v, cnt, mx);
fl = 1;
}
if (!fl)cnt = 1;
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
*/
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 'int deep(int, int, int&, int, int)':
shymbulak.cpp:56: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:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
shymbulak.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
shymbulak.cpp:88: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:126: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:133:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:142: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 |
5 ms |
5240 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5248 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5696 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5696 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
235 ms |
21688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
