// alright, so this is how this problem works (i think):
// because this graph has the special property that it only contains a simple cycle, we can view it as a "ring",
// where the simple cycle is the ring, and we root subtrees in each node of the ring.
//
// now we combine these two cases:
// 1. diameters for each subtree rooted in ring nodes, which can be done with rerooting i think;
// 2. max depth node in A's subtree with max depth node in B's subtree, where A < B and A and B are ring nodes.
//
// and i think there's a sub-quadratic way to do this..
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
class DSU {
private:
int n;
std::vector<int> t;
std::vector<int> sz;
public:
DSU(int n): n(n) {
t.assign(n,0); std::iota(t.begin(), t.end(), 0);
sz.assign(n,1);
}
int Find(int k) {
if (t[k]!=k) return t[k] = Find(t[k]);
return t[k];
}
int Unite(int a, int b) {
int ra = Find(a);
int rb = Find(b);
if (ra==rb) {
return 0;
}
if (sz[ra]<sz[rb]) {
std::swap(ra,rb);
}
sz[ra] += sz[rb];
t[rb] = ra;
return 1;
}
};
int gs;
std::vector<std::vector<int>> graph_adj_list;
std::vector<std::vector<int>> span_adj_list;
std::vector<std::pair<int,int>> edges;
std::vector<bool> edge_in_span;
std::vector<int> ring;
// first = max, second = cnt
std::vector<std::pair<int,int64_t>> ring_subtree_diam;
std::vector<std::pair<int,int>> ring_subtree_max_depth;
std::vector<bool> in_ring;
void read_graph() {
std::cin >> gs;
graph_adj_list.resize(gs);
span_adj_list.resize(gs);
edge_in_span.assign(gs,0);
edges.reserve(gs);
in_ring.assign(gs,0);
for (int i = 0, a, b; i < gs; i++) {
std::cin >> a >> b; --a, --b;
graph_adj_list[a].emplace_back(b);
graph_adj_list[b].emplace_back(a);
edges.emplace_back(a,b);
}
}
void find_ring() {
const auto build_spanning_tree = [&]() {
DSU dsu(gs);
for (int i = 0; i < gs; i++) {
auto [a, b] = edges[i];
if (dsu.Unite(a,b)) {
edge_in_span[i] = 1;
span_adj_list[a].emplace_back(b);
span_adj_list[b].emplace_back(a);
}
}
};
const auto get_path = [&](int a, int b) {
std::vector<int> last(gs,-2);
std::queue<int> q;
q.emplace(a);
last[a] = -1;
while (!q.empty()) {
int k = q.front();
q.pop();
for (const auto& i : span_adj_list[k]) {
if (last[i]==-2) {
last[i] = k;
q.emplace(i);
}
}
}
std::vector<int> ret;
int k = b;
while (k!=-1) {
ret.emplace_back(k);
k = last[k];
}
return ret;
};
build_spanning_tree();
for (int i = 0; i < gs; i++) {
if (!edge_in_span[i]) {
auto [a, b] = edges[i];
ring = get_path(a,b);
for (const auto& node : ring) {
in_ring[node] = 1;
}
break;
}
}
#ifdef DBG
for (const auto& i : ring) {
std::cout << i+1 << " ";
}
std::cout << "\n";
#endif
}
void solve_subtrees() {
const auto solve_subtree = [&](int root) {
ring_subtree_diam.emplace_back(-1,1);
ring_subtree_max_depth.emplace_back(-1,1);
std::unordered_map<int, std::pair<int,int>> dp;
const std::function<void(int,int)> dfs = [&](int k, int p) {
dp[k].first = 0;
dp[k].second = 1;
std::vector<std::pair<int,int>> max_depth_children;
for (const auto& i : graph_adj_list[k]) {
if (!in_ring[i]&&i!=p) {
dfs(i,k);
if (dp[k].first < dp[i].first + 1) {
dp[k].first = dp[i].first + 1;
dp[k].second = 0;
}
if (dp[k].first == dp[i].first + 1) {
dp[k].second += dp[i].second;
}
max_depth_children.emplace_back(dp[i]);
}
}
// update max depth + count
if (k==root) {
if (ring_subtree_max_depth.back().first < dp[k].first) {
ring_subtree_max_depth.back().first = dp[k].first;
ring_subtree_max_depth.back().second = 0;
}
if (ring_subtree_max_depth.back().first == dp[k].first) {
ring_subtree_max_depth.back().second += dp[k].second;
}
}
// update diameter + count
std::sort(max_depth_children.begin(),max_depth_children.end(),std::greater<std::pair<int,int>>());
if (max_depth_children.size() == 1) {
if (ring_subtree_diam.back().first < max_depth_children[0].first + 1) {
ring_subtree_diam.back().first = max_depth_children[0].first + 1;
ring_subtree_diam.back().second = 0;
}
if (ring_subtree_diam.back().first == max_depth_children[0].first + 1) {
ring_subtree_diam.back().second += max_depth_children[0].second;
}
}
else if (max_depth_children.size() > 1) {
int l = 0, r = 0;
while (r+1<max_depth_children.size()&&(r<1||max_depth_children[r+1].first==max_depth_children[1].first)) {
++r;
}
if (ring_subtree_diam.back().first < max_depth_children[0].first + max_depth_children[1].first + 2) {
ring_subtree_diam.back().first = max_depth_children[0].first + max_depth_children[1].first + 2;
ring_subtree_diam.back().second = 0;
}
if (ring_subtree_diam.back().first == max_depth_children[0].first + max_depth_children[1].first + 2) {
if (max_depth_children[0].first == max_depth_children[1].first) {
std::vector<int64_t> pfx(max_depth_children.size(),0);
for (int i = 0; i <= r; i++) {
if (i-1>=0) {
pfx[i] += pfx[i-1];
}
pfx[i] += max_depth_children[i].second;
}
for (int i = 1; i <= r; i++) {
ring_subtree_diam.back().second += 1LL*max_depth_children[i-1].second*(pfx[r]-pfx[i-1]);
}
}
else {
for (int i = 1; i <= r; i++) {
ring_subtree_diam.back().second += 1LL*max_depth_children[0].second*max_depth_children[i].second;
}
}
}
}
};
dfs(root,-1);
};
for (const auto& root : ring) {
solve_subtree(root);
}
#ifdef DBG
for (int i = 0; i < ring.size(); i++) {
std::cout << ring[i]+1 << "\n";
std::cout << ring_subtree_diam[i].first << " " << ring_subtree_diam[i].second << "\n";
std::cout << ring_subtree_max_depth[i].first << " " << ring_subtree_max_depth[i].second << "\n";
}
#endif
// case 1: path is in one tree
std::pair<int,int64_t> ans(0,0);
for (int i = 0; i < ring.size(); i++) {
if (ans.first < ring_subtree_diam[i].first) {
ans.first = ring_subtree_diam[i].first;
ans.second = 0;
}
if (ans.first == ring_subtree_diam[i].first) {
ans.second += ring_subtree_diam[i].second;
}
}
// case 2: tree A -> ring -> tree B
std::deque<std::pair<int,int>> dq;
for (int i = 0; i < ring.size(); i++) {
while (!dq.empty()&&dq.front().first<ring_subtree_max_depth[i].first-i) {
dq.pop_back();
}
dq.emplace_back(ring_subtree_max_depth[i].first-i,i);
}
for (int i = ring.size(); i < 2*ring.size(); i++) {
while (!dq.empty()&&i-dq.front().second>ring.size()/2) {
dq.pop_front();
}
for (int j = 0; j < dq.size(); j++) {
if (dq[j].first+i==dq.front().first+i) {
if (ans.first < dq[j].first+i+ring_subtree_max_depth[i%ring.size()].first) {
ans.first = dq[j].first+i+ring_subtree_max_depth[i%ring.size()].first;
ans.second = 0;
}
if (ans.first == dq[j].first+i+ring_subtree_max_depth[i%ring.size()].first) {
ans.second += 1LL*ring_subtree_max_depth[dq[j].second%ring.size()].second*ring_subtree_max_depth[i%ring.size()].second;
}
}
else {
break;
}
}
while (!dq.empty()&&dq.front().first<ring_subtree_max_depth[i%ring.size()].first-i) {
dq.pop_back();
}
dq.emplace_back(ring_subtree_max_depth[i%ring.size()].first-i,i);
}
std::cout << ans.second << "\n";
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
read_graph();
find_ring();
solve_subtrees();
}
Compilation message
shymbulak.cpp: In lambda function:
shymbulak.cpp:194:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
194 | while (r+1<max_depth_children.size()&&(r<1||max_depth_children[r+1].first==max_depth_children[1].first)) {
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
shymbulak.cpp:193:9: warning: unused variable 'l' [-Wunused-variable]
193 | int l = 0, r = 0;
| ^
shymbulak.cpp: In function 'void solve_subtrees()':
shymbulak.cpp:242:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
242 | for (int i = 0; i < ring.size(); i++) {
| ~~^~~~~~~~~~~~~
shymbulak.cpp:254:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
254 | for (int i = 0; i < ring.size(); i++) {
| ~~^~~~~~~~~~~~~
shymbulak.cpp:260:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
260 | for (int i = ring.size(); i < 2*ring.size(); i++) {
| ~~^~~~~~~~~~~~~~~
shymbulak.cpp:261:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
261 | while (!dq.empty()&&i-dq.front().second>ring.size()/2) {
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
shymbulak.cpp:265:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
265 | for (int j = 0; j < dq.size(); j++) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1368 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1116 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
17256 KB |
Output is correct |
| 2 |
Correct |
62 ms |
18496 KB |
Output is correct |
| 3 |
Correct |
38 ms |
15168 KB |
Output is correct |
| 4 |
Correct |
43 ms |
14156 KB |
Output is correct |
| 5 |
Correct |
41 ms |
14164 KB |
Output is correct |
| 6 |
Correct |
123 ms |
33228 KB |
Output is correct |
| 7 |
Correct |
86 ms |
25288 KB |
Output is correct |
| 8 |
Correct |
102 ms |
27984 KB |
Output is correct |
| 9 |
Correct |
95 ms |
28240 KB |
Output is correct |
| 10 |
Correct |
78 ms |
28920 KB |
Output is correct |
| 11 |
Correct |
93 ms |
38060 KB |
Output is correct |
| 12 |
Correct |
99 ms |
40024 KB |
Output is correct |
