连珠线

 

题意

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

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

思路

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

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

sample_1

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

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

那么我们的答案就可以像下面这样的更新,假设点 $v$ 为点 $u$ 的子节点,$len$ 为两点间的距离。 \(F[u][0] = \sum_v \max(F[v][0] ,F[v][1] + len) \\ F[u][1] = F[u][0] + \max_v(F[v][0] + len - \max(F[v][0] , F[v][1] + len))\) 为了方便观察,我们不妨定义 $div = div(u,v) = \max(F[v][0] , F[v][1] + len)$

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

\(F[u][0] = \sum_v \max div \\ F[u][1] = F[u][0] + \max_v (F[v][0] + len - div)\) 那么我们最终 $F[root][0]$ 就是以我们随意选择的点作为根的最大值。

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

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

sample_2

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

首先我们定义 $H[0 / 1]$ 表示当以 $v$ 为根的时候,$v$ 的子树为 $u$ 时候的 $F[u][0 / 1]$ 。

那么首先我们可以得知 \(H[0] = G[u][0] - div \\ H[1] = H[0] + \max_{x \in son(u)}(len(u , x) - div(u,x)) \\ 或者通过 G[u][1] 来写。 \\ H[1] = G[u][1] - div + other\) 我们发现,当且仅当 $len + F[v][0] - div$ 是所有 $u$ 的子树中最大的时候,我们的 $H[1]$ 才需要计算其剩余的子树最大值,所以我们不妨记录最大值与次大值$MX[u][0 / 1]$。 0 表示最大值 , 1 表示次大值。

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

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

1
2
3
4
5
6
7
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;
}

那么此时,我们就得到了以 $u$ 作为点 $v$ 的子树的 $H[0 / 1]$ 那么我们的 \(G[v][0] = F[v][0] + \max(H[0],H[1] + len)\)

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

1
2
3
4
5
6
7
8
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]$ 并不是必要的。

那么最终的代码就是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#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;
}
algorithm