图片炸了，难过。本地也没有存。

Sol.

一道很经典的基环树上dp题。~~调了一年~~。

首先，如果没有环的话，这就是一道简单的求树上重心的题目。众所周知，树的重心一定在直径的中点上。

但是现在在一个基环树上做，应该怎么求呢？我们先画一个图：

为了方便，我们先设边权全部为 \(1\)。

首先，我们可以想到断一条环上的边，然后求断边后的树的直径。

略证：考虑到直径一定不会经过一整个环，所以依次断边后求直径一定不会漏掉真正的直径。

这样的复杂度是 \(O(n^2)\) 的，我们考虑一下如何优化。

在刚刚的过程中，我们从环上的第一条边一直到最后一条边依次断开，而我们每次断开都要重新计算一次直径，这中间显然是有重合的部分的，于是我们可以考虑用类似于 dp 的东西优化。

考虑有两种情况:

直径没有经过环；
直径经过了环。

第一个情况很好搞，第二种情况略有麻烦，也是我们刚刚复杂度的瓶颈所在。

先上结论：

记 \(pre_i\) 表示 \(i\) 点之前某以环上节点为根节点的子树的直径加上该点距离环上 \(1\) 号点的距离的最大值；
记 \(suf_i\) 表示 \(i\) 点之后某以环上节点为根节点的子树的直径加上该点距离环上 \(m\) 号点的距离的最大值；
记 \(pres_i\) 表示 \(i\) 点之前环上某两节点的子树直径加上两点之间的距离的最大值；
记 \(sufs_i\) 表示 \(i\) 点之后环上某两节点的子树直径加上两点之间的距离的最大值；
记 \(w_{(i,j)}\) 表示 \(i,j\) 两点的距离。

那么第 \(i\) 号点的答案即为 \(\max\{pre_i, suf_{i+1}, pres_i+sufs_{i+1}+w_{(1,m)}\}\)。

最终答案即为 \(\min\limits_{i=1}^{m-1}\{\max\{pre_i, suf_{i+1}, pres_i+sufs_{i+1}+w_{(1,m)}\}\}\)

是不是到现在已经有些晕了？没关系，我们从图上举例说明一下。

例如，我们现在有一只删了一条环边 \((4,5)\) 的基环树。

我们仔细复盘一下刚刚的几句话。

先看 \(pre_i\) 和 \(suf_i\)。由于两个很像，所以重点解释 \(pre_i\)。

记 \(pre_i\) 表示 \(i\) 点之前 \(//\) 某以环上节点为根节点的子树的直径 \(//\) 加上该点距离环上 \(1\) 号点的距离 \(//\) 的最大值。

形式化的来说，我们要找的就是：

\(pre_i=\max\limits_{j=1}^{i}\{dep_j+w_{(1,j)}\}\)

来看张图。

可能有多种方案，图中仅展示一种。

图中绿色的部分即为 \(pre_4\)，橙色的部分即为 \(suf_5\)。

可以看出来 \(pre_i\) 和 \(suf_i\) 其实就是一棵子树的直径 \(+\) 它前面（后面）的链的长度。

接下来再看看 \(pres_i\) 和 \(sufs_i\)，同样重点解释 \(pres_i\)。

记 \(pres_i\) 表示 \(i\) 点之前 \(//\) 环上某两节点的子树直径 \(//\) 加上两点之间的距离的最大值。

形式化的来说，我们要找的就是：

\(pres_i=\max\limits_{j=1}^{i}\{dep_i+dep_j+w_{(i,j)}\}\)

再来看张图。

可能有多种方案，图中仅展示一种。

图中蓝色的部分即为 \(pres_4\)，黄色的部分即为 \(sufs_5\)。

好，弄清楚这 \(4\) 个，我们来看看结果的式子：

那么第 \(i\) 号点的答案即为 \(\max\{pre_i, suf_{i+1}, pres_i+sufs_{i+1}+w_{(1,m)}\}\)。

我们考虑到删掉边 \((i,i+1)\) 的时候，直径有三种可能：

直径在 \([1,i]\) 之间；
直径在 \([i+1,m]\) 之间；
直径跨过了边 \((1,m)\)。

对于第一种情况，我们惊喜地发现，\(pres_i\) 即为我们所求。

对于第二种情况，我们再次惊喜地发现，\(sufs_{i+1}\) 即为我们所求。

对于第三种情况，我们发现，由于 \(pre_i\) 一直延伸到 \(i\)，\(suf_{i+1}\) 一直延伸到 \(m\)，所以我们再加上 \(w_{(1,m)}\) 即可，也就是 \(pre_i+suf_{i+1}+w_{(1,m)}\)。

最后我们遍历一遍，统计最小值即可。

Code

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 7;

struct Edge
{
    int to, nxt, w;
}e[MAXN << 1];

int n;

int head[MAXN << 1], ent;
int fa[MAXN], tnt, dfn[MAXN], dis[MAXN];
bool iscyc[MAXN];
int cyc[MAXN], cnt, cycdis[MAXN];
ll dep[MAXN];
ll pre[MAXN], suf[MAXN], presub[MAXN], sufsub[MAXN];
ll ans = 0;

void add_edge(int u, int v, int w)
{
    e[++ent].to = v;
    e[ent].w = w;
    e[ent].nxt = head[u];
    head[u] = ent;
}

void dfs1(int u)
{
    dfn[u] = ++tnt;
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa[u]) continue;
        if(!dfn[v])
        {
            fa[v] = u;
            dis[v] = e[i].w;
            dfs1(v);
        }
        else if(dfn[v] > dfn[u])
        {
            for(; v != u; v = fa[v])
            {
                iscyc[v] = true;
                cyc[++cnt] = v;
                cycdis[cnt] = dis[v];
            }
            iscyc[u] = true;
            cyc[++cnt] = u;
            cycdis[cnt] = e[i].w;
        }
    }
}

void dfs2(int u, int father)
{
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(!iscyc[v] && v != father)
        {
            dfs2(v, u);
            ans = max((ll)dep[u] + dep[v] + e[i].w, ans);
            dep[u] = max(dep[u], dep[v] + e[i].w);
        }
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add_edge(a, b, c);
        add_edge(b, a, c);
        fa[i] = i;
    }
    dfs1(1);
    for(int i = 1; i <= cnt; i++)
        dfs2(cyc[i], 0);
    ll sum = 0, maxdep = 0;
    for(int i = 1; i <= cnt; i++)
    {
        sum += cycdis[i - 1];
        pre[i] = max(pre[i - 1], dep[cyc[i]] + sum);
        presub[i] = max(presub[i - 1], sum + maxdep + dep[cyc[i]]);
        maxdep = max(maxdep, dep[cyc[i]] - sum);
    }
    sum = maxdep = 0;
    int tmp = cycdis[cnt];
    cycdis[cnt] = 0;
    for(int i = cnt; i; i--)
    {
        sum += cycdis[i];
        suf[i] = max(suf[i + 1], dep[cyc[i]] + sum);
        sufsub[i] = max(sufsub[i + 1], sum + maxdep + dep[cyc[i]]);
        maxdep = max(maxdep, dep[cyc[i]] - sum);
    }
    ll res = presub[cnt];
    for(int i = 1; i < cnt; i++)
        res = min(max(max(presub[i], sufsub[i + 1]), pre[i] + suf[i + 1] + tmp), res);
    printf("%.1lf", (double)max(ans, res) / 2.0);
    return 0;
}

NOI2013 快餐店

Sol.

Code