#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;
/**
- we have a single cycle in this graph
- we calculate the maximum depth and its count in every tree spanning from the cycle
- we use a segmentree on a cyclic vector (we will double it)
- now we solve independently for every tree spaning from the cycle
**/
const int MAX_N = 2e5;
vector <int> cycle;
int state[1 + MAX_N];
bool fix[1 + MAX_N];
vector <int> v;
vector <int> gr[1 + MAX_N];
void dfs_cycle (int node, int par) {
state[node] = 1;
v.pb (node);
for (int vec : gr[node])
if (vec != par) {
if (state[vec] == 0)
dfs_cycle (vec, node);
else if (state[vec] == 1) {
int idx = ((int) v.size ()) - 1;
while (idx >= 0 && v[idx] != vec) {
cycle.pb (v[idx]);
idx--;
}
cycle.pb (vec);
}
}
v.pop_back ();
state[node] = 2;
}
struct Node {
int value;
ll cnt;
};
Node max_depth[1 + MAX_N];
Node ans;
Node join (Node l, Node r) {
Node x;
x = l;
if (x.value == r.value)
x.cnt += r.cnt;
else if (x.value < r.value)
x = r;
return x;
}
void dfs_depth (int node, int par) {
max_depth[node] = {0, 1};
for (int son : gr[node])
if (son != par && not fix[son]) {
dfs_depth (son, node);
ans = join (ans, {max_depth[node].value + max_depth[son].value + 1, max_depth[node].cnt * max_depth[son].cnt});
max_depth[node] = join (max_depth[node], {max_depth[son].value + 1, max_depth[son].cnt});
}
}
struct LazySegTree {
vector <Node> seg;
vector <int> lazy;
int n;
LazySegTree (int n) {
this->n = n;
seg.resize (1 + 4 * n);
lazy.resize (1 + 4 * n);
}
void push (int node) {
if (lazy[node]) {
int left_node = node * 2, right_node = node * 2 + 1;
seg[left_node].value += lazy[node];
seg[right_node].value += lazy[node];
lazy[left_node] += lazy[node];
lazy[right_node] += lazy[node];
lazy[node] = 0;
}
}
void build (int node, int lb, int rb, vector <Node> &v) {
if (lb == rb) {
seg[node] = {v[lb - 1].value + lb - 1, v[lb - 1].cnt};
return;
}
int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
build (left_node, lb, mid, v);
build (right_node, mid + 1, rb, v);
seg[node] = join (seg[left_node], seg[right_node]);
}
void update (int node, int lb, int rb, int q_left, int q_right, int to_add) {
if (q_left <= lb && rb <= q_right) {
seg[node].value += to_add;
lazy[node] += to_add;
return;
}
int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
push (node);
if (q_left <= mid)
update (left_node, lb, mid, q_left, q_right, to_add);
if (q_right >= mid + 1)
update (right_node, mid + 1, rb, q_left, q_right, to_add);
seg[node] = join (seg[left_node], seg[right_node]);
}
Node query (int node, int lb, int rb, int q_left, int q_right) {
if (q_left > q_right)
return {0, 0};
if (q_left <= lb && rb <= q_right)
return seg[node];
int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
push (node);
Node ans = {0, 0};
if (q_left <= mid)
ans = join (ans, query (left_node, lb, mid, q_left, q_right));
if (q_right >= mid + 1)
ans = join (ans, query (right_node, mid + 1, rb, q_left, q_right));
return ans;
}
};
/**
6
1 2
1 3
2 4
4 3
4 5
4 6
**/
int main () {
ios::sync_with_stdio (false);
cin.tie (0); cout.tie (0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
gr[x].pb (y);
gr[y].pb (x);
}
dfs_cycle (1, 0);
for (int x : cycle)
fix[x] = true;
for (int x : cycle)
dfs_depth (x, 0);
vector <Node> elements;
for (int x : cycle)
elements.pb (max_depth[x]);
for (int x : cycle)
elements.pb (max_depth[x]);
int m = cycle.size ();
int sz = elements.size ();
LazySegTree helper (sz);
helper.build (1, 1, sz, elements);
int from_right = m / 2;
for (int i = 1; i <= m; i++) {
Node ans_right = helper.query (1, 1, sz, i + 1, i + from_right);
Node best = {ans_right.value + elements[i - 1].value, ans_right.cnt * elements[i - 1].cnt};
ans = join (ans, best);
helper.update (1, 1, sz, 1, i, 1);
helper.update (1, 1, sz, i + 1, sz, -1);
}
cout << ans.cnt << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 6 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 11 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 12 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 13 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 14 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 15 |
Correct |
4 ms |
5100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5356 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 5 |
Correct |
5 ms |
5356 KB |
Output is correct |
| 6 |
Correct |
5 ms |
5356 KB |
Output is correct |
| 7 |
Correct |
6 ms |
5356 KB |
Output is correct |
| 8 |
Correct |
6 ms |
5356 KB |
Output is correct |
| 9 |
Correct |
6 ms |
5356 KB |
Output is correct |
| 10 |
Correct |
6 ms |
5356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
9868 KB |
Output is correct |
| 2 |
Correct |
81 ms |
10348 KB |
Output is correct |
| 3 |
Correct |
91 ms |
25700 KB |
Output is correct |
| 4 |
Correct |
52 ms |
11628 KB |
Output is correct |
| 5 |
Correct |
46 ms |
11500 KB |
Output is correct |
| 6 |
Correct |
179 ms |
15852 KB |
Output is correct |
| 7 |
Correct |
124 ms |
14060 KB |
Output is correct |
| 8 |
Correct |
94 ms |
17260 KB |
Output is correct |
| 9 |
Correct |
97 ms |
17516 KB |
Output is correct |
| 10 |
Correct |
87 ms |
19296 KB |
Output is correct |
| 11 |
Correct |
101 ms |
17376 KB |
Output is correct |
| 12 |
Correct |
114 ms |
17888 KB |
Output is correct |
