14DUnreviewed1900GPT-5.4 (high)

Two Paths

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

Progressive nudges

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 $e$ , 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 $e=(u,v)$ , the best profit after deleting it is

\operatorname{diam}(C_u) \cdot \operatorname{diam}(C_v),

where $C_u$ and $C_v$ are the two components containing $u$ and $v$ .

That is the whole solution: iterate over every edge $(u,v)$ , temporarily forbid crossing it, compute the diameter of the component reachable from $u$ , compute the diameter of the component reachable from $v$ , and maximize their product. Use the standard double DFS/BFS trick for diameter: from any node find the farthest node $a$ , then from $a$ find the farthest distance. With $n \le 200$ , this brute force is easily fast enough: $O(n^2)$ .

Observation 1: an optimal pair is separated by some edge

Take any optimal two vertex-disjoint paths $P$ and $Q$ . In a tree, there is a unique simple path connecting the vertex set of $P$ to the vertex set of $Q$ . Pick any edge $e$ on that connector.

That edge cannot belong to either repaired path. After deleting $e$ , the tree splits into two components, and $P$ lies entirely in one component while $Q$ 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.

Observation 2: for a fixed cut, the best path in a component is its diameter

Suppose deleting edge $e$ gives components $C_1$ and $C_2$ . If one repaired path must lie in each component, then the maximum possible path length in a component is exactly its diameter:

D_1 = \operatorname{diam}(C_1), \qquad D_2 = \operatorname{diam}(C_2).

So for this particular cut, the best profit is

D_1 \cdot D_2.

If a component has only one vertex, its diameter is $0$ , which is perfectly fine: a one-city path has length $0$ .

Why this gives the exact answer

Define

F = \max_{e} \left(\operatorname{diam}(C_1(e)) \cdot \operatorname{diam}(C_2(e))\right),

where $C_1(e)$ and $C_2(e)$ are the two components after removing edge $e$ .

We claim $F$ is exactly the answer.

$F$ is achievable. For any edge $e$ , take a diameter path in each of the two components. They are in different components, so they are automatically vertex-disjoint.
No optimal solution can beat $F$ . Take an optimal pair of disjoint paths $P, Q$ . By Observation 1, some edge $e$ separates them. Therefore $|P| \le \operatorname{diam}(C_1(e)), \qquad |Q| \le \operatorname{diam}(C_2(e)).$ Multiplying, $|P|\,|Q| \le \operatorname{diam}(C_1(e)) \cdot \operatorname{diam}(C_2(e)) \le F.$

So the answer is exactly

\boxed{\max_{e=(u,v)} \operatorname{diam}(C_u) \cdot \operatorname{diam}(C_v)}.

Computing a component diameter

For a tree component, use the standard double DFS/BFS trick:

Start from any vertex in the component.
Find the farthest vertex $a$ .
Start from $a$ and find the farthest distance again.
That distance is the diameter.

This works because in a tree, a farthest vertex from an arbitrary start is an endpoint of some diameter.

When processing an original edge $(u,v)$ , simply pretend that edge does not exist:

starting from $u$ explores exactly one component;
starting from $v$ explores the other one.

Compute both diameters and update the answer with their product.

Complexity

There are $n-1$ edges. For each edge, we compute two diameters, and each diameter takes two DFS traversals over at most $n$ vertices.

So the total complexity is

O(n) \text{ per edge } \times O(n) \text{ edges } = O(n^2),

with $O(n)$ memory.

Given $n \le 200$ , 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';
}

View on Codeforces Back to the list