P3647 连珠线 题解

题意

我们有 n 个珠子，我们可以选择一枚珠子作为我们的起点。然后我们可以选择用红线将新珠子与已有的珠子连起来，或者在用红线连起来的两个点间加入一个点，并将红线替换为两个蓝线。

蓝线的长度即为我们的分数，求最大得分。

思路

首先我们任意选取一个节点作为根。

那么一定会出现下图所示的的状况。

那么对于一个节点我们有两种情况，要么是两个蓝线的终点，要么不是，那么因此我们用 $F[u][0\mathrm{/}1]F[u][0\; /\; 1]$ 来表示。

其中 0 表示不是中点，1表示是中点。

那么我们的答案就可以像下面这样的更新，假设点 $vv$ 为点 $uu$ 的子节点，$lenlen$ 为两点间的距离。

为了方便观察，我们不妨定义 $div=div(u,v)=\max (F[v][0],F[v][1]+len)div\; =\; div(u,v)\; =\; \backslash max(F[v][0]\; ,\; F[v][1]\; +\; len)$

那么方程也就变成了，如下的式子

那么我们最终 $F[root][0]F[root][0]$ 就是以我们随意选择的点作为根的最大值。

由于以不同根作为最大值不同，因此我们需要定义另一个最大值，$G[u][0\mathrm{/}1]G[u][0\; /\; 1]$ 具体意义为以点 $uu$ 为根的最大值。

那么我们发现对于 $uu$ 节点的一颗子树 $vv$ 而言。包括了两个部分。如下图所示。

我们假定我们已经知道 $G[u][0]G[u][0]$ 和 $G[u][1]G[u][1]$ 我们现在需要推导 $G[v][0]G[v][0]$ 与 $G[v][1]G[v][1]$

首先我们定义 $H[0\mathrm{/}1]H[0\; /\; 1]$ 表示当以 $vv$ 为根的时候，$vv$ 的子树为 $uu$ 时候的 $F[u][0\mathrm{/}1]F[u][0\; /\; 1]$ 。

那么首先我们可以得知

我们发现，当且仅当 $len+F[v][0]-divlen\; +\; F[v][0]\; -\; div$ 是所有 $uu$ 的子树中最大的时候，我们的 $H[1]H[1]$ 才需要计算其剩余的子树最大值，所以我们不妨记录最大值与次大值$MX[u][0\mathrm{/}1]MX[u][0\; /\; 1]$。 0 表示最大值 , 1 表示次大值。

如果写成第二个式子我们同样也可以发现如上的问题。

那么这样子我们的 $H[1]H[1]$ 就可以变成了如下的形式。其中注释部分也是成立的。

if(MX[u][0] == len + F[v][0] - div) {
    H[1] = H[0] + MX[u][1];
    // H[1] = G[u][1] - div - MX[u][0] + MX[u][1];
} else {
    H[1] = H[0] + MX[u][0];
    // H[1] = G[u][1] - div;
}

那么此时，我们就得到了以 $uu$ 作为点 $vv$ 的子树的 $H[0\mathrm{/}1]H[0\; /\; 1]$ 那么我们的

然后我们再求出其作为子树是否可以更新 $MXMX$ 的值，最后更新 $G[v][1]G[v][1]$ 的值。

long long MXD = H[0] + len - max(H[0] , H[1] + len);
if(MXD > MX[u][0]) {
    MX[u][1] = MX[u][0];
    MX[u][0] = MXD;
} else if (MXD > MX[u][1]) {
    MX[u][1] = MXD;
}
G[v][1] = G[v][0] + MX[u][0];

通过上述，我们发现其实 $G[v][1]G[v][1]$ 并不是必要的。

那么最终的代码就是

#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;

const int N = 2e5 + 10;
vector<pair<int, int>> E[N];
LL F[N][2];
LL G[N][2];
LL H[N][2];
LL MX[N][2];

void dfs(int u, int fa = -1) {
    F[u][0] = 0;
    MX[u][0] = MX[u][1] = F[u][1] = -(1ll << 40);
    for (auto [v, len] : E[u]) {
        if (v == fa) continue;
        dfs(v, u);
        F[u][0] += max(F[v][0], F[v][1] + len);
    }

    for (auto [v, len] : E[u]) {
        if (v == fa) continue;
        LL div = len + F[v][0] - max(F[v][0], F[v][1] + len);
        if (div > MX[u][0]) {
            MX[u][1] = MX[u][0];
            MX[u][0] = div;
        } else if (div > MX[u][1]) {
            MX[u][1] = div;
        }
    }

    F[u][1] = F[u][0] + MX[u][0];
}

void dfs2(int u, int fa = -1) {
    for (auto [v, len] : E[u]) {
        if (v == fa) continue;
        H[u][0] = G[u][0] - max(F[v][0], F[v][1] + len);

        LL div = len + F[v][0] - max(F[v][0], F[v][1] + len);

        if (div == MX[u][0]) {
            H[u][1] =
                G[u][1] - MX[u][0] + MX[u][1] - max(F[v][0], F[v][1] + len);
        } else {
            H[u][1] = G[u][1] - max(F[v][0], F[v][1] + len);
        }

        G[v][0] = F[v][0] + max(H[u][0], len + H[u][1]);
        int MXD = len + H[u][0] - max(H[u][0], H[u][1] + len);
        if (MXD > MX[v][0]) {
            MX[v][1] = MX[v][0];
            MX[v][0] = MXD;
        } else if (MXD > MX[v][1]) {
            MX[v][1] = MXD;
        }
        G[v][1] = G[v][0] + MX[v][0];
        dfs2(v, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y, len;
        cin >> x >> y >> len;
        E[x].push_back({y, len});
        E[y].push_back({x, len});
    }

    long long ans = -1;

    // cerr << "ROOT = " << 1 << '\n';

    dfs(1);
    G[1][0] = F[1][0], G[1][1] = F[1][1];

    dfs2(1);
    for (int i = 1; i <= n; i++) {
        // cerr << "I = " << i << " G = " << G[i][0] << '\n';
        ans = max(G[i][0], ans);
    }

    cout << ans << '\n';

    return 0;
}