CF835F 题解

· · 题解

此题解纪念我这一题一遍过。

传送门

题意：给定基环树（带边权），问删掉一条边之后，直径最短是多少。

显然为了保证连通，我们只能删环上的边。

我们需要找出这个环：

struct Edge {
    int to;
    ll val;
    Edge(int t = 0, ll v = 0) {
        to = t;
        val = v;
    }
};
vector<Edge> e[N];

// 环上的一个点st，环上一共cnt个点，i号点在环上的上一个点为pre[i]，下一个nxt[i]，i->nxt[i]的边权是wei[i] 
int st, cnt = 0, pre[N], nxt[N], wei[N];

bool inCir[N] = {}; // inCir[i] = true表示i在环上

bool vis[N] = {}, flag = false; // vis[i]表示i访问过，flag表示找到了环
void srh(int x, int pr) {
    vis[x] = true;
    for (int i = 0; i < e[x].size() && !flag; i++)
        if (e[x][i].to != pr) {
            int v = e[x][i].to, tw = e[x][i].val;
            if (!vis[v])
                nxt[x] = v, wei[x] = tw, srh(v, x);
            else { // 若访问过，则说明找到了环
                nxt[x] = v, wei[x] = tw, pre[v] = x, st = v;
                flag = true;
                for (int i = st; true; i = nxt[i]) {
                    cnt++, inCir[i] = true;
                    if (nxt[i] == st)
                        break;
                }
            }
        }
}

因为基环树可以看作是森林的根结点相连，我们可以把基环树的直径分成两种情况分别求：

  1. 是某一棵树内部的直径；

  2. 是两棵树组合得到的直径。

上面两种情况分别求出来，然后两种情况取 \max 即可。

【某一棵树内部的直径】

既然已经找出了环，我们只需要遍历环上每一个点，求出对应的树里面的直径即可。

我用的是 DP 求。

ll dth[N] = {}, mxd[N] = {}, smxd[N] = {}; //深度，最长链，次长链 
ll dp_tree[N] = {}; //dp_tree[u]表示u的子树内的直径 
void dfs_tree(int x, int pr) {
//  cout << x << ' ' << pr << endl;
    for (auto i: e[x])
        if (i.to != pr && !inCir[i.to]) {
            dth[i.to] = dth[x] + i.val;
            dfs_tree(i.to, x);
            if (i.val + mxd[i.to] > mxd[x]) {
                smxd[x] = mxd[x];
                mxd[x] = i.val + mxd[i.to];
            }
            else if (i.val + mxd[i.to] > smxd[x])
                smxd[x] = i.val + mxd[i.to];
        }
    for (auto v: e[x]) {
        if (v.to != pr && !inCir[v.to])
            dp_tree[x] = max(dp_tree[x], dp_tree[v.to]);
    }
    dp_tree[x] = max(dp_tree[x], mxd[x] + smxd[x]);
}

这里不仅求了树内部的直径，同时还记录的最长链 mxd。这个最长链就是第二种情况要用到的。

【两棵树组合的直径】

如果枚举环上的点对，至少是 O(n^2) 的，而且还要考虑删的边，无法接受。

我们转而考虑删了环上的哪条边，然后对所有删边的情况取 \min 就是删边的最佳方案。（注意这里是 \min）

我们记整个环是 c_1c_2\dots c_k，环的边是 c_ic_{i+1}(i<k) 和 c_kc_1。

  1. 如果删的是 c_ic_{i+1}(i<k)。

    这种情况下的直径，能分成三种可能：

    1. 两棵树都属于 c_1\sim c_i 中。

      我们考虑预处理出一个 L[i]：表示 c_1\sim c_i 中任取两棵树，得到的路径最长是多少；R[i] 类似表示 c_i\sim c_k 中的答案。

      这里我们只考虑 L[i] 怎么计算，这也是一个 DP。

      如果第 i 棵树不选，L[i]=L[i-1]；

      如果第 i 棵树选了，L[i]=\displaystyle\max_{j=1}^{i-1}(mxd[i]+mxd[j]+dis(j,i))。

      前一种情况简单，关注第二种。首先 dis(j,i) 可以通过记录环上的边的前缀和 s，变成 s[i-1]-s[j-1]（这里 -1 是因为我写的是 s[i] 表示从 1 走到 i+1）。

      这样式子就变成 L[i]=\displaystyle\max_{j=1}^{i-1}(mxd[i]+mxd[j]+s[i-1]-s[j-1])=mxd[i]+s[i-1]+\displaystyle\max_{j=1}^{i-1}(mxd[j]-s[j-1]).

      于是我们再预处理一个 mxl[i]=\displaystyle\max_{j=1}^i(mxd[j]-s[j-1])，可以简单递推得到。

      则 L[i]=\max(L[i-1],mxd[i]+s[i-1]+mxl[i-1])。

    2. 两棵树都属于 c_{i+1}\sim c_k 中。

      这种情况和上面类似。也预处理一个 R[i],mxr[i]。

    3. 一颗在 c_1\sim c_i，另一颗在 c_{i+1}\sim c_k。

      对于这种情况，假设我们 c_1\sim c_i 选了 c_p，则 c_p 对直径的贡献是 mxd[p]+s[p-1]；同理 c_{i+1}\sim c_k 中选了 c_q 的贡献是 mxd[q]+s[k-1]-s[q-1]。

      于是 $ans=\max(mxd[p]+s[p-1]+mxd[q]-s[q-1])+s[k]$，我们再次预处理 $mxl2[i]=\max(mxd[i]+s[i-1]),mxr2[i]=\max(mxd[i]-s[i-1])$ 即可。

  2. 删的是 c_kc_1，刚好可以用上面预处理的 L[k] 直接得到。

这道题还是相当考验码力的，但是模块分得清楚也不是特别难写。（就是模块也太多了）

【Code】

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
typedef long long ll;

int n;
struct Edge {
    int to;
    ll val;
    Edge(int t = 0, ll v = 0) {
        to = t;
        val = v;
    }
};
vector<Edge> e[N];

// 环上的一个点st，环上一共cnt个点，i号点在环上的上一个点为pre[i]，下一个nxt[i]，i->nxt[i]的边权是wei[i] 
int st, cnt = 0, pre[N], nxt[N], wei[N];

bool inCir[N] = {}; // inCir[i] = true表示i在环上

bool vis[N] = {}, flag = false; // vis[i]表示i访问过，flag表示找到了环
void srh(int x, int pr) {
    vis[x] = true;
    for (int i = 0; i < e[x].size() && !flag; i++)
        if (e[x][i].to != pr) {
            int v = e[x][i].to, tw = e[x][i].val;
            if (!vis[v])
                nxt[x] = v, wei[x] = tw, srh(v, x);
            else { // 若访问过，则说明找到了环
                nxt[x] = v, wei[x] = tw, pre[v] = x, st = v;
                flag = true;
                for (int i = st; true; i = nxt[i]) {
                    cnt++, inCir[i] = true;
                    if (nxt[i] == st)
                        break;
                }
            }
        }
}

ll dth[N] = {}, mxd[N] = {}, smxd[N] = {}; //深度，最长链，次长链 
ll dp_tree[N] = {}; //dp_tree[u]表示u的子树内的直径 
void dfs_tree(int x, int pr) {
//  cout << x << ' ' << pr << endl;
    for (auto i: e[x])
        if (i.to != pr && !inCir[i.to]) {
            dth[i.to] = dth[x] + i.val;
            dfs_tree(i.to, x);
            if (i.val + mxd[i.to] > mxd[x]) {
                smxd[x] = mxd[x];
                mxd[x] = i.val + mxd[i.to];
            }
            else if (i.val + mxd[i.to] > smxd[x])
                smxd[x] = i.val + mxd[i.to];
        }
    for (auto v: e[x]) {
        if (v.to != pr && !inCir[v.to])
            dp_tree[x] = max(dp_tree[x], dp_tree[v.to]);
    }
    dp_tree[x] = max(dp_tree[x], mxd[x] + smxd[x]);
}

ll ans, ans2; 

ll a[N], w[N];
ll s[N];
//s[i]=w[1]+...+w[i]

ll L[N], R[N], mxl[N], mxr[N];
ll mxl2[N], mxr2[N];

int main() {
    cin >> n;
    for (int i = 1, u, v, tw; i <= n; i++) {
        cin >> u >> v >> tw;
        e[u].push_back(Edge(v, tw));
        e[v].push_back(Edge(u, tw));
    }
    srh(1, 0);
    for (int i = st; ; i = nxt[i]) {
        dth[i] = mxd[i] = 0;
        dfs_tree(i, 0);
        ans = max(ans, dp_tree[i]);
        if (nxt[i] == st)
            break;
    }
    //此时，令a[i]=mxd[i]，要做环形 DP了
    for (int cc = 1, i = st; ; i = nxt[i], cc++) {
        a[cc] = mxd[i];
        w[cc] = wei[i]; //w[i]是从i->i+1 
        if (nxt[i] == st)
            break;
    }
    s[0] = 0;
    for (int i = 1; i <= cnt; i++)
        s[i] = s[i - 1] + w[i]; 
    //删除某条边，同时最小化 max(a[x]+a[y]+dist(x,y))
    /*
    1. 1~i = L[i] = max(L[i-1], j~i) = max(L[i-1], s[i-1]-s[j-1]+a[i]+a[j]) = max(L[i-1], max{a[j]-s[j-1]} + a[i]+s[i-1])
        令mxl[i] = max{a[i]-s[i-1]}，则 L[i]=max(L[i-1], mxl[i-1] + a[i] + s[i-1]) 

    2. i~n = R[i] = max(R[i+1], i~j) = max(R[i+1], a[i]+a[j]+s[j-1]-s[i-1]) = max(R[i+1], a[i]-s[i-1] + max{a[j]+s[j-1]})
        令mxr[i] = max{a[j]+s[j-1]}，则 R[i]=max(R[i+1], a[i] - s[i-1] + mxr[i+1]) 
    3. i~i+1 = max{a[i]+s[i-1] + a[j]-s[j-1]} + s[n]
        令 mxl2[i] = max{a[i]+s[i-1]}, mxr2[i]=max{a[j]-s[j-1]}
        则 i~i+1 = max{mxl2[i] + mxr2[i+1]} + s[cnt]
    */

    L[0] = mxl[0] = mxl2[0] = ~0x3f3f3f3f3f3f3f3f;
    for (int i = 1; i <= cnt; i++) {
        L[i] = max(L[i - 1], mxl[i - 1] + a[i] + s[i - 1]);
        mxl[i] = max(mxl[i - 1], a[i] - s[i - 1]);
    }

    R[cnt + 1] = mxr[cnt + 1] = mxr2[cnt + 1] = ~0x3f3f3f3f3f3f3f3f;
    for (int i = cnt; i >= 1; i--) {
        R[i] = max(R[i + 1], a[i] - s[i - 1] + mxr[i + 1]);
        mxr[i] = max(mxr[i + 1], a[i] + s[i - 1]);
    }

    for (int i = 1; i <= cnt; i++)
        mxl2[i] = max(mxl2[i - 1], a[i] + s[i - 1]);
    for (int i = cnt; i >= 1; i--)
        mxr2[i] = max(mxr2[i + 1], a[i] - s[i - 1]);

    ans2 = 0x3f3f3f3f3f3f3f3f;

//  for (int i = st; ; i = nxt[i]) {
//      cout << wei[i] << ' ';
//      if (nxt[i] == st)
//          break;
//  }
//  puts("");
//  for (int i = 1; i <= cnt; i++)
//      cout << mxl2[i] << ' ';
//  puts("");
//  for (int i = 1; i <= cnt; i++)
//      cout << mxr2[i] << ' ';
//  puts("");
    ans2 = min(ans2, L[cnt]);
    for (int i = 1; i < cnt; i++) { //枚举删的是 i-i+1
        ans2 = min(ans2, max(max(L[i], R[i + 1]), mxl2[i] + mxr2[i + 1] + s[cnt]));
    }
//  puts("");
    cout << max(ans, ans2) << endl;
    return 0;
}
.