题目地址：洛谷：【P3647】[APIO2014]连珠线 – 洛谷、BZOJ：Problem 3677. — [Apio2014]连珠线

题目描述

在达芬奇时代，有一个流行的儿童游戏称为连珠线。当然，这个游戏是关于珠子和线的。线是红色或蓝色的，珠子被编号为 1 到 n 。这个游戏从一个珠子开始，每次会用如下方式添加一个新的珠子：
Append(w, v)：一个新的珠子 w 和一个已经添加的珠子 v 用红线连接起来。
Insert(w, u, v)：一个新的珠子 w 插入到用红线连起来的两个珠子 u, v 之间。具体过程是删去 u, v 之间红线，分别用蓝线连接 u, w 和 w, v 。
每条线都有一个长度。游戏结束后，你的最终得分为蓝线长度之和。
给你连珠线游戏结束后的游戏局面，只告诉了你珠子和链的连接方式以及每条线的长度，没有告诉你每条线分别是什么颜色。
你需要写一个程序来找出最大可能得分。即，在所有以给出的最终局面结束的连珠线游戏中找出那个得分最大的，然后输出最大可能得分。

题意简述

有一种游戏，用珠子和红蓝两种颜色的绳子玩。游戏的初始局面只有一颗珠子，你可以做下面两种操作：

1. 把一颗新珠子用红线接到局面上已有的珠子上
2. 在局面上已有的红线连接的两个珠子间用蓝线连接第三颗珠子，同时断掉之前的红线

给你最终局面的样子，但没有说明线分别是什么颜色的，要求你找到一种合法的方案，使得蓝线的长度之和最长。

输入输出格式

输入格式：
第一行一个正整数 n ，表示珠子的数量。珠子从 1 到 n 编号。
接下来 n-1 行每行三个整数 ai,bi,ci 。保证 1≤ai<bi≤n 。 1≤ci≤10000 。表示 ai 号珠子和 bi 号珠子间连了长度为 ci 的线。

输出格式：
输出一个整数，表示最大可能得分。

输入输出样例

输入样例#1：

5
1 2 10
1 3 40
1 4 15
1 5 20

输出样例#1：

60

输入样例#2：

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34

输出样例#2：

140

说明

【样例描述1】
可以通过如下方式获得 60 分：首先从 3 号珠子开始。
把 5 和 3 连起来。（线长度任意）
在 3 和 5 之间插入 1 。（线长分别为 40 和 20 ）。
把 2 和 1 用长度为 10 的线连起来。
把 4 和 1 用长度为 15 的线连起来。
【限制与约定】
第一个子任务共 13 分，满足 1≤n≤10 。
第二个子任务共 15 分，满足 1≤n≤200 。
第三个子任务共 29 分，满足 1≤n≤10000 。
第四个子任务共 43 分，满足 1≤n≤200000 。

题解

参考资料：bzoj3677【APIO2014】连珠线 – CSDN博客
我们观察到一个特征，如果称两条蓝线中间的点为中间点的话，不存在蓝线是中间点的两个儿子边的情况，只存在蓝线分别连向一个儿子和中间点的父亲的情况。这是显然的，因为从根开始玩这个游戏，每次实际上是在给跟扩充儿子，两条蓝线可以看做之前的一条红线，而这条红线是连接父亲和儿子的，因此只存在一种形态。
观察到这个特征后，我们可以设计一个树形DP，用$dp[u][0]$表示点$u$不作为蓝线的中心点的方案最大值，而$dp[u][1]$表示$u$作为中心点的方案最大值。容易得到以下转移方程
$$ \begin{aligned} dp[u][0] &= \sum_{v \in \mathrm{son}(u)} \max \{ dp[v][0], dp[v][1] + w(u, v) \} \\ dp[u][1] &= \max_{v \in \mathrm{son}(u)} \{ dp[u][0] – \max \{ dp[v][0], dp[v][1] + w(u, v) \} + dp[v][0] + w(u, v) \} \end{aligned} $$
对于树根为每一个点的情况都做一遍DP，取树根的$dp[rt][0]$最大值即为答案，但是每一次DP的复杂度是$O(n)$的，直接枚举根重新DP则会使复杂度达到$O(n^2)$，只有28分。我们需要优化枚举根重新DP的复杂度。
我们考虑讨论换根操作对根处DP值的影响。如果当前根在$u$处，现在，我们将根换为$u$的一个儿子$v$，则会造成如下影响：

1. $dp[u][0]$与$dp[u][1]$中要删去$v$对其的贡献
2. $dp[v][0]$与$dp[u][1]$要加入$u$对其的贡献

对于加入贡献与删去$dp[u][0]$中的贡献来说比较好办，只需要进行简单的加减或是类似DP时的更新操作即可，但是$dp[u][1]$并不太好办了，因为这里求了个最大值。我们需要一个次大值，因此需要在第一遍DP的时候把次大值也存起来，这样，在换根的时候就可以用次大值来代替答案。我们考虑用DFS做换根的操作，这样就无需讨论跨很多点换根的情况，换根仅发生在父亲和儿子之间，且可以后退操作。如此，我们实现了$O(1)$的换根操作，把复杂度降为$O(n)$了。
实现上，有一种简化的方法，即在处理$dp[u][1]$的时候不把$dp[u][0]$加进去，需要用到的时候再加进去。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 200005;

int n;

struct Edge {
    int to, w;
};

std::vector<Edge> gra[MAXN];
int dp[MAXN][5], ans;

inline void update(int u, int v, int w) {
    if(w >= dp[u][1]) {
        dp[u][2] = dp[u][1]; dp[u][1] = w;
        dp[u][4] = dp[u][3]; dp[u][3] = v;
    } else if(w >= dp[u][2]) {
        dp[u][2] = w; dp[u][4] = v;
    }
}

inline void dfs(int u, int fa) {
    dp[u][1] = dp[u][2] = -2e9;
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i].to;
        if(v == fa) continue;
        dfs(v, u);
        int w = std::max(dp[v][0], dp[v][0] + dp[v][1] + gra[u][i].w);
        dp[u][0] += w;
        update(u, v, dp[v][0] + gra[u][i].w - w);
    }
}

inline void dfs1(int u, int fa) {
    ans = std::max(ans, dp[u][0]);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i].to;
        if(v == fa) continue;
        int bdp0 = dp[v][0], bdp1 = dp[v][1], bdp2 = dp[v][2], bdp3 = dp[v][3], bdp4 = dp[v][4];
        int w = std::max(dp[v][0], dp[v][0] + dp[v][1] + gra[u][i].w),
            t = dp[u][3] == v,
            dp0 = dp[u][0] - w,
            nw = std::max(dp0, dp[u][0] + dp[u][t + 1] - w + gra[u][i].w);
        dp[v][0] += nw;
        update(v, u, dp0 + gra[u][i].w - nw);
        dfs1(v, u);
        dp[v][0] = bdp0; dp[v][1] = bdp1; dp[v][2] = bdp2; dp[v][3] = bdp3; dp[v][4] = bdp4;
    }
}

int main() {
    n = readint();
    for(int i = 1, u, v, w; i < n; i++) {
        u = readint(); v = readint(); w = readint();
        gra[u].push_back(Edge {v, w});
        gra[v].push_back(Edge {u, w});
    }
    dfs(1, 0);
    dfs1(1, 0);
    printf("%d", ans);
    return 0;
}