Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Forget the product for a second. Take any two vertex-disjoint paths in a tree. Because the graph is a tree, there is a unique simple path connecting these two sets of vertices. What could you do with an edge on that connector?
If you remove an edge lying on the connector between the two chosen paths, the paths end up in different connected components. So instead of choosing two paths directly, try fixing a separating edge first.
For a fixed removed edge , the tree splits into two components. Now the problem becomes independent on the two sides: choose one path in the left component and one path in the right component. What is the longest possible path inside a tree component?
For a component, the best path length is its diameter. So for an edge , the best profit after deleting it is
where and are the two components containing and .
That is the whole solution: iterate over every edge , temporarily forbid crossing it, compute the diameter of the component reachable from , compute the diameter of the component reachable from , and maximize their product. Use the standard double DFS/BFS trick for diameter: from any node find the farthest node , then from find the farthest distance. With , this brute force is easily fast enough: .
Take any optimal two vertex-disjoint paths and . In a tree, there is a unique simple path connecting the vertex set of to the vertex set of . Pick any edge on that connector.
That edge cannot belong to either repaired path. After deleting , the tree splits into two components, and lies entirely in one component while lies entirely in the other. So every valid answer is witnessed by some cut edge. That is the whole trick. No black magic, just cut one damn edge.
Suppose deleting edge gives components and . If one repaired path must lie in each component, then the maximum possible path length in a component is exactly its diameter:
So for this particular cut, the best profit is
If a component has only one vertex, its diameter is , which is perfectly fine: a one-city path has length .
Define
where and are the two components after removing edge .
We claim is exactly the answer.
So the answer is exactly
For a tree component, use the standard double DFS/BFS trick:
This works because in a tree, a farthest vertex from an arbitrary start is an endpoint of some diameter.
When processing an original edge , simply pretend that edge does not exist:
Compute both diameters and update the answer with their product.
There are edges. For each edge, we compute two diameters, and each diameter takes two DFS traversals over at most vertices.
So the total complexity is
with memory.
Given , this is ridiculously safe.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int n;
vector<vector<int>> g;
pair<int, int> farthestNode(int start, int bu, int bv) {
pair<int, int> best = {0, start};
auto dfs = [&](auto&& self, int u, int p, int dist) -> void {
if (dist > best.first) best = {dist, u};
for (int v : g[u]) {
if (v == p) continue;
if ((u == bu && v == bv) || (u == bv && v == bu)) continue;
self(self, v, u, dist + 1);
}
};
dfs(dfs, start, 0, 0);
return best;
}
int diameter(int start, int bu, int bv) {
auto a = farthestNode(start, bu, bv);
auto b = farthestNode(a.second, bu, bv);
return b.first;
}
int main() { setIO();
cin >> n;
g.assign(n + 1, vector<int>());
vector<pair<int, int>> edges;
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
edges.push_back({u, v});
}
int ans = 0;
for (auto [u, v] : edges) {
int d1 = diameter(u, u, v);
int d2 = diameter(v, u, v);
ans = max(ans, d1 * d2);
}
cout << ans << '\n';
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int n;
vector<vector<int>> g;
pair<int, int> farthestNode(int start, int bu, int bv) {
pair<int, int> best = {0, start};
auto dfs = [&](auto&& self, int u, int p, int dist) -> void {
if (dist > best.first) best = {dist, u};
for (int v : g[u]) {
if (v == p) continue;
if ((u == bu && v == bv) || (u == bv && v == bu)) continue;
self(self, v, u, dist + 1);
}
};
dfs(dfs, start, 0, 0);
return best;
}
int diameter(int start, int bu, int bv) {
auto a = farthestNode(start, bu, bv);
auto b = farthestNode(a.second, bu, bv);
return b.first;
}
int main() { setIO();
cin >> n;
g.assign(n + 1, vector<int>());
vector<pair<int, int>> edges;
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
edges.push_back({u, v});
}
int ans = 0;
for (auto [u, v] : edges) {
int d1 = diameter(u, u, v);
int d2 = diameter(v, u, v);
ans = max(ans, d1 * d2);
}
cout << ans << '\n';
}