| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1091691 | 2024-09-21T19:59:01 Z | xnqs | 관광지 (IZhO14_shymbulak) | C++17 | 0 ms | 0 KB |
// 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++) {
for (int j = 1; j <= std::min(300,ring.size()/2); j++) {
if (ans.first < ring_subtree_max_depth[(i-j+ring.size())%ring.size()].first + ring_subtree_max_depth[i].first + j) {
ans.first = ring_subtree_max_depth[(i-j+ring.size())%ring.size()].first + ring_subtree_max_depth[i].first + j;
ans.second = 0;
}
if (ans.first == ring_subtree_max_depth[(i-j+ring.size())%ring.size()].first + ring_subtree_max_depth[i].first + j) {
ans.second += 1LL*ring_subtree_max_depth[(i-j+ring.size())%ring.size()].second*ring_subtree_max_depth[i].second;
}
}
}
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();
}