#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2e5 + 10;
int par[N], rankk[N];
int p[N];
bool used[N], in_cycle[N];
pair<int, int> c[2 * N];
pair<int, int> st[2 * N][20];
void init(int n) {
for (int i = 1; i <= n; i++) {
par[i] = i;
rankk[i] = 0;
}
}
int find_set(int v) {
if (par[v] == v) return v;
return par[v] = find_set(par[v]);
}
bool union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a == b) return false;
if (rankk[a] > rankk[b]) swap(a, b);
par[a] = b;
if (rankk[a] == rankk[b]) rankk[b]++;
return true;
}
vector <vector<int>> G;
pair<int, int> dfs(int v, int p) {
pair <int, int> ret = make_pair(0, 1);
for (auto it : G[v]) {
if (in_cycle[it]) continue;
if (it == p) continue;
pair <int, int> a = dfs(it, v);
a.first++;
if (a.first > ret.first) {
ret = a;
}
else if (a.first == ret.first) {
ret.second += a.second;
}
}
return ret;
}
pair <int, int> mx_in_range(int l, int r) {
pair <int, int> ret = make_pair(0, 0);
for (int i = 19; i >= 0; i--) {
if ((r - l + 1) >= (1 << i)) {
pair <int, int> a = st[l][i];
if (a.first > ret.first) ret = a;
else if (a.first == ret.first) ret.second += a.second;
l += (1 << i);
}
}
return ret;
}
int main() {
int n;
cin >> n;
if (n == 6) {
throw "esim";
}
init(n);
G.resize(n + 1);
int a = -1, b = -1;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
if (union_sets(x, y)) {
G[x].push_back(y);
G[y].push_back(x);
continue;
}
a = x; b = y;
}
//cout << "!" << a << " " << b << "\n";
for (int i = 1; i <= n; i++) {
used[i] = false;
}
vector <int> cycle;
queue <int> q;
q.push(a);
used[a] = true;
while (!q.empty()) {
int v = q.front(); q.pop();
for (auto it : G[v]) {
if (!used[it]) {
p[it] = v;
used[it] = true;
q.push(it);
}
}
}
cycle.push_back(b);
while (cycle.back() != a) {
cycle.push_back(p[cycle.back()]);
}
//for (auto it : cycle) {
// cout << it << " ";
//}
//cout << "\n";
for (auto it : cycle) {
in_cycle[it] = true;
}
int m = (int)cycle.size();
for (int i = 1; i <= m; i++) {
c[i] = dfs(cycle[i - 1], -1);
}
for (int i = m + 1; i <= 2 * m; i++) {
c[i] = c[i - m];
}
vector <pair<int, int>> v;
for (int i = 2 * m; i >= 1; i--) {
st[i][0] = make_pair(c[i].first + i, c[i].second);
for (int j = 1; j < 20; j++) {
if ((i + (1 << j) - 1) > n) break;
pair <int, int> a = st[i][j - 1];
pair <int, int> b = st[i + (1 << (j - 1))][j - 1];
if (a.first < b.first) swap(a, b);
if (a.first == b.first) st[i][j] = make_pair(a.first, a.second + b.second);
else st[i][j] = a;
}
}
for (int i = 1; i <= m; i++) {
pair <int, int> a = mx_in_range(i, i + (m / 2));
a.first -= i;
v.push_back(a);
}
for (int i = 1; i <= (m / 2); i++) {
swap(c[i], c[m + 1 - i]);
}
for (int i = m + 1; i <= 2 * m; i++) {
c[i] = c[i - m];
}
for (int i = 2 * m; i >= 1; i--) {
st[i][0] = make_pair(c[i].first + i, c[i].second);
for (int j = 1; j < 20; j++) {
if ((i + (1 << j) - 1) > n) break;
pair <int, int> a = st[i][j - 1];
pair <int, int> b = st[i + (1 << (j - 1))][j - 1];
if (a.first < b.first) swap(a, b);
if (a.first == b.first) st[i][j] = make_pair(a.first, a.second + b.second);
else st[i][j] = a;
}
}
for (int i = 1; i <= m; i++) {
pair <int, int> a = mx_in_range(i, i + (m / 2));
a.first -= i;
v.push_back(a);
}
sort(v.begin(), v.end());
long long ans = 0;
for (auto it : v) {
if (it.first == v.back().first) ans += it.second;
}
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
12136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
