#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;
}
pair<int, int> mx[N];
vector <vector<int>> child;
int w;
vector <int> vert;
vector <pair<int, long long>> v;
void dfss(int v, int p) {
vert.push_back(v);
mx[v] = make_pair(0, 1);
for (auto it : G[v]) {
if (it == p) continue;
if (in_cycle[it]) continue;
dfss(it, v);
if (mx[it].first + 1 > mx[v].first) {
mx[v] = make_pair(mx[it].first + 1, mx[it].second);
}
else if (mx[it].first + 1 == mx[v].first) {
mx[v] = make_pair(mx[v].first, mx[v].second + mx[it].second);
}
child[v].push_back(it);
}
}
pair <int, long long> f(int v) {
vert.clear();
pair <int, long long> ret = make_pair(0, 1);
dfss(v, -1);
for (auto it : vert) {
if (mx[it].first > ret.first) {
ret = mx[it];
}
else if (mx[it].first == ret.first) {
ret.second += mx[it].second;
}
vector <pair<int, long long>> cur;
for (auto j : child[it]) {
cur.push_back(mx[j]);
}
sort(cur.begin(), cur.end());
reverse(cur.begin(), cur.end());
if (cur.size() <= 1) continue;
if (cur[0].first == cur[1].first) {
int last = 1;
for (int i = 2; i < (int)cur.size(); i++) {
if (cur[i].first == cur[0].first) last = i;
}
long long v = 0;
for (int i = 0; i <= last; i++) {
v += cur[i].second;
}
pair <int, long long> qwe;
qwe.first = 2 * cur[0].first + 2;
for (int i = 0; i < last; i++) {
v -= cur[i].second;
qwe.second += (cur[i].second * 1ll * v);
}
if (qwe.first > ret.first) ret = qwe;
else if (qwe.first == ret.first) ret.second += qwe.second;
continue;
}
long long v = 0;
for (int i = 1; i < (int)cur.size(); i++) {
if (cur[i].first == cur[1].first) v += cur[i].second;
}
pair <int, long long> qwe;
qwe.first = cur[0].first + cur[1].first + 2;
qwe.second = (cur[0].second * 1ll * v);
if (qwe.first > ret.first) ret = qwe;
else if (qwe.first == ret.first) ret.second += qwe.second;
}
return ret;
}
int main() {
int n = -1;
cin >> n;
//if (n == -1) {
// throw "esim";
//}
init(n);
G.resize(n + 1);
child.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();
//if (m < 3) {
// throw "esim";
//}
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];
}
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) > 2 * m) 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 + 1, i + (m / 2));
a.first -= i;
a.first += c[i].first;
v.push_back(make_pair(a.first, c[i].second * 1ll * a.second));
}
for (auto it : cycle) {
v.push_back(f(it));
}
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 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 7 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 8 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 9 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 10 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 11 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 12 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 13 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 14 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 15 |
Correct |
3 ms |
8540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
2 ms |
8652 KB |
Output is correct |
| 5 |
Correct |
4 ms |
9048 KB |
Output is correct |
| 6 |
Correct |
4 ms |
9308 KB |
Output is correct |
| 7 |
Correct |
5 ms |
9100 KB |
Output is correct |
| 8 |
Correct |
5 ms |
9052 KB |
Output is correct |
| 9 |
Correct |
4 ms |
9052 KB |
Output is correct |
| 10 |
Correct |
6 ms |
9052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
17868 KB |
Output is correct |
| 2 |
Correct |
79 ms |
18124 KB |
Output is correct |
| 3 |
Correct |
73 ms |
36168 KB |
Output is correct |
| 4 |
Correct |
68 ms |
18072 KB |
Output is correct |
| 5 |
Correct |
83 ms |
18260 KB |
Output is correct |
| 6 |
Correct |
171 ms |
26312 KB |
Output is correct |
| 7 |
Correct |
133 ms |
22192 KB |
Output is correct |
| 8 |
Correct |
145 ms |
27836 KB |
Output is correct |
| 9 |
Correct |
149 ms |
28004 KB |
Output is correct |
| 10 |
Correct |
134 ms |
29520 KB |
Output is correct |
| 11 |
Correct |
115 ms |
31300 KB |
Output is correct |
| 12 |
Correct |
121 ms |
35676 KB |
Output is correct |
