好的，这道题是 NOI 2013 的「快餐店」问题，是一道经典的 基环树（环套树） 上的最优化问题。我将为你提供完整的解题思路与代码实现。

---

题目重述

我们有一个 $N$ 个点 $N$ 条边的 连通无向图（即基环树），快餐店可以设在 任意一个点 或 任意一条边的任意位置（不一定是端点）。
目标是：
找到一个位置，使得 距离该位置最远的顾客 的距离 最小，并输出这个最小距离。

换句话说，就是找到基环树的 最小直径 的“中心”。

---

问题分析

1. 基环树结构

• 给定 $N$ 个点 $N$ 条边的连通图，必定有且仅有一个环。
• 去掉环上的边，剩下的每个连通块都是一棵树（称为“外向树”）。

2. 问题转化

设快餐店的位置为 $X$，定义 $f(X)$ 为所有点到 $X$ 的最远距离。
我们要找 $\min f(X)$，其中 $X$ 可以是任意点或任意边上的任意位置。

重要性质：
对于一棵树，如果只能设在点上，最优解是 树的中心（直径的中点），此时最远距离 = $\lceil \frac{\text{直径}}{2} \rceil$。
如果允许设在边上，那么最优解可以设在直径路径的 中点（不一定是端点），此时最远距离 = $\frac{\text{直径}}{2}$。

对于基环树，最优解可能在：

1. 某棵外向树内部（不经过环）
2. 环上某个点
3. 环上某条边的中间

---

核心思路

步骤 1：找环

使用 DFS 或拓扑排序找环，这里推荐用拓扑排序（不断删去度数为 1 的点）得到环上的点。

步骤 2：预处理每棵外向树

对每个环上的点 $u$，将其作为根，向外遍历其子树（不经过环上的其他点），计算：

• $d[u]$：从 $u$ 出发，在其子树中能走到的最远距离（即该外向树的深度）。
• 同时求出该子树的直径，更新全局答案的候选。

步骤 3：环上问题转化为序列问题

将环展开成链 $c_1, c_2, \dots, c_m$（$m$ 为环上点数），并记录环上相邻点之间的边权 $w_i$（连接 $c_i$ 与 $c_{i+1}$，$w_m$ 连接 $c_m$ 与 $c_1$）。

定义：

• $A[i] = d[c_i]$：环上点 $i$ 的外向树深度
• $S[i]$：从 $c_1$ 按顺时针方向走到 $c_i$ 的环上距离前缀和（$S[1] = 0$）。

如果快餐店设在环上，那么最远距离可能来自：

1. 某棵外向树内部（已经在外向树内部计算过）
2. 通过环走到另一棵外向树的距离

对于环上两个点 $i$ 和 $j$，它们之间的环上距离有两种：

• 顺时针：$|S[j] - S[i]|$
• 逆时针：$totalLen - |S[j] - S[i]|$ 其中 $totalLen$ 是环的总长度。

对于快餐店设在环上某处（点或边），最远距离可以表示为： [ \max_{i} \left( d[i] + \text{环上某点到 } i \text{ 的最短距离} \right) ] 我们要最小化这个最大值。

---

关键优化

这是一个环形问题，可以破环为链，复制一倍。

定义： [ \text{dist}(i,j) = \min(S[j] - S[i],\ totalLen - (S[j] - S[i])) ] 但直接枚举是 $O(m^2)$ 的，需要优化。

重要观察：
如果快餐店设在环上某处，那么对于环上每个点 $i$，最远距离是： [ \max_{j} \left( d[j] + \text{dist}(i,j) \right) ] 我们要找 $i$（可以是点或边的中间）使得这个最大值最小。

破环为链技巧：
将环展开成 $c_1, c_2, \dots, c_m, c_{m+1}, \dots, c_{2m}$，其中 $c_{k+m} = c_k$，$S[k+m] = S[k] + totalLen$。
那么对于任意 $i < j \le i+m$，环上 $c_i$ 到 $c_j$ 的顺时针距离是 $S[j] - S[i]$，逆时针距离是 $totalLen - (S[j] - S[i])$。

设快餐店位置在 $c_i$ 和 $c_{i+1}$ 之间的边上某处（包括端点），那么对于环上点 $c_j$，最短距离是： [ \min(S[j] - S[i],\ totalLen - (S[j] - S[i])) ] 更一般地，如果设在 $c_i$ 顺时针 $x$ 距离处（$0 \le x \le w_i$），那么到 $c_j$ 的顺时针距离是 $S[j] - (S[i] + x)$，逆时针类似。

但是，我们可以发现一个性质：最优位置一定在环上某条边的中点或端点上。因此，只需枚举边和点即可。

---

经典解法

更简洁的思路：

1. 如果最优解在某棵外向树内部
   那么答案就是该树的直径除以 2。我们可以在预处理时求出所有外向树的直径，取最大值 $D_{\text{tree}}$。

2. 如果最优解在环上
   考虑破环为链，复制一倍。
   对于环上两个点 $i$ 和 $j$，它们之间走环的最短路径不超过环长的一半。
   因此，我们可以考虑环上顺序，用单调队列优化求： [ \max_{j} \left( d[j] + S[j] \right) \quad \text{和} \quad \max_{j} \left( d[j] - S[j] \right) ] 然后枚举断开环的位置，计算该情况下的直径，取最小值。

最终答案 = $\max( \text{外向树最大直径}, \text{环上最优解} )$ 吗？
不对，因为这是两个不同的情况，我们要取的是所有可能的最小值，所以： [ \text{答案} = \min\left( \frac{\text{外向树最大直径}}{2},\ \text{环上最优解} \right) ] 但是，环上最优解也可能比外向树内部直径的一半更小，所以要综合比较。

实际上，最终答案是： [ \max\left( \text{所有外向树的最大直径},\ \text{环上最优解直径} \right) \div 2 ] 因为快餐店可以设在边的中间，所以直径可以折半。

更准确地说：

• 如果最优解在外向树内部，答案 = 该树的直径 / 2
• 如果最优解在环上，答案 = 环上最优解直径 / 2

取两者较小值？不，我们要找全局最小化最远距离，所以是取所有情况的最小值。

---

标准解法流程

1. 找环（拓扑排序）
2. 对每个环上点 DFS 求外向树深度 $d[i]$ 和该子树的直径
3. 破环为链，复制一倍，求前缀和 $S$
4. 对于每个 $i$（$1 \le i \le m$），考虑断开环上 $i$ 到 $i+1$ 的边，此时基环树变成一棵树，其直径可能为：
   • 某棵外向树自身的直径
   • 环上两点 $u,v$ 通过链连接的距离：$d[u] + d[v] + S[v] - S[u]$（$u < v$）
5. 对于固定的 $i$，$u,v$ 必须位于断开后的同一侧，即 $i \le u < v \le i+m-1$。
   此时求 $d[u] + d[v] + S[v] - S[u] = (d[u] - S[u]) + (d[v] + S[v])$ 的最大值。
   可以用单调队列维护 $d[v] + S[v]$ 的最大值，枚举 $u$ 更新答案。
6. 对所有断开位置 $i$ 求得的直径取最小值，然后除以 2，即为环上最优解。
7. 最终答案 = $\min( \text{环上最优解},\ \text{所有外向树最大直径}/2 )$

---

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
const LL INF = 1e18;

int n;
vector<pair<int, LL>> g[N];
int deg[N];
bool on_cycle[N];
vector<int> cycle;
LL d[N], tree_dia = 0;
LL S[N * 2], A[N * 2];

void find_cycle() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        deg[i] = g[i].size();
        if (deg[i] == 1) q.push(i);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto &e : g[u]) {
            int v = e.first;
            if (--deg[v] == 1) q.push(v);
        }
    }
    // 现在 deg > 1 的点都在环上
    int start = -1;
    for (int i = 1; i <= n; i++) {
        on_cycle[i] = (deg[i] > 1);
        if (on_cycle[i]) start = i;
    }
    // 提取环的顺序
    cycle.clear();
    int cur = start, prev = -1;
    do {
        cycle.push_back(cur);
        int nxt = -1;
        for (auto &e : g[cur]) {
            int v = e.first;
            if (on_cycle[v] && v != prev) {
                nxt = v;
                break;
            }
        }
        prev = cur;
        cur = nxt;
    } while (cur != start);
}

LL dfs_depth(int u, int p) {
    LL max1 = 0, max2 = 0;
    for (auto &e : g[u]) {
        int v = e.first;
        LL w = e.second;
        if (v == p || on_cycle[v]) continue;
        LL dis = dfs_depth(v, u) + w;
        if (dis > max1) {
            max2 = max1;
            max1 = dis;
        } else if (dis > max2) {
            max2 = dis;
        }
    }
    tree_dia = max(tree_dia, max1 + max2);
    return max1;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int a, b; LL l;
        scanf("%d%d%lld", &a, &b, &l);
        g[a].push_back({b, l});
        g[b].push_back({a, l});
    }

    find_cycle();
    int m = cycle.size();

    // 计算环上每个点的外向树深度
    for (int i = 0; i < m; i++) {
        int u = cycle[i];
        d[u] = dfs_depth(u, -1);
    }

    // 计算环上边权
    vector<LL> edge_len(m);
    for (int i = 0; i < m; i++) {
        int u = cycle[i];
        int v = cycle[(i + 1) % m];
        for (auto &e : g[u]) {
            if (e.first == v) {
                edge_len[i] = e.second;
                break;
            }
        }
    }

    // 破环为链，复制一倍
    for (int i = 0; i < m * 2; i++) {
        int idx = i % m;
        A[i + 1] = d[cycle[idx]];
        if (i > 0) {
            S[i + 1] = S[i] + edge_len[(i - 1) % m];
        }
    }

    // 单调队列优化求环上最优解
    LL ans_cycle = INF;
    deque<int> dq;
    for (int i = 1; i <= m * 2; i++) {
        while (!dq.empty() && dq.front() <= i - m) dq.pop_front();
        if (!dq.empty()) {
            int j = dq.front();
            ans_cycle = min(ans_cycle, A[i] + A[j] + S[i] - S[j]);
        }
        while (!dq.empty() && A[dq.back()] - S[dq.back()] <= A[i] - S[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }

    // 最终答案
    LL ans = max(tree_dia, ans_cycle);
    printf("%.1lf\n", ans / 2.0);

    return 0;
}

---

算法复杂度

• 找环：$O(N)$
• 求外向树深度：$O(N)$
• 单调队列处理环：$O(m)$，$m$ 为环上点数
• 总复杂度：$O(N)$，可以通过 $N \le 10^5$ 的数据

---

总结

这道题考察了 基环树的处理技巧、破环为链、单调队列优化 以及 树的直径性质，是一道综合性很强的图论题目。核心在于将环上问题转化为序列问题，并用单调队列高效求解。