介绍

换根DP是一种特殊的树形DP。主要特点在于需要进行两次DFS。

第一次DFS:固定任意节点(一般为 $1$)为根。对于每一个节点 $u$,仅考虑 $u$ 的subtree,求出这样的答案 $dp[u]$。

第二次DFS:令最终答案为 $ans[u]$,则可知 $ans[1] = dp[1]$。然后我们需要通过已知的 $ans[u]$,来推出它的child $ans[to]$ 的值。一般我们由 $ans[u]$ 来推导 $ans[to]$ 时,需要考虑到换根时 $to$ 子树内的贡献,和子树外的贡献 变化。

套路

我们考虑一下一种general的情况:从 $u$ 换根到 $v$

此时我们一定位于 dfs(u) 中,并且已经求出了 $ans[u]$。现在要求 $ans[v]$。(注:这里的 $ans[u]$ 是广义的,代表 $u$ 相关的信息。不一定真的是最终的 $ans$,比如例4)

那么换根前是这样:

img

换根后,是这样:

img

步骤如下:

  1. 基于 $ans[u]$,将 $u$ 的child $v$ 所带来的贡献删掉,得到 $dp2[u]$。
  2. 基于 $dp[v]$,将 $u$ 作为一个新的child 加给 $v$(实际上,就是将 $dp2[u]$ 的贡献加给 $dp[v]$),得到 $ans[v]$。

• 注意,这里的 $dp2[u]$ 实际上是一个临时的变量。对于每一个 $v$ 而言,$dp2[u]$ 互不相同。

例题

例1 洛谷P3478 [POI2008]STA-Station

题意

给定 $n$ 个节点的树,求一个节点 $u$ 使得 $u$ 到其他节点的距离和最大。

即,求出 $u$,使得 $\sum\limits_v d(u,v)$ 最大。

题解

首先固定 $1$ 为根,进行一次DFS。

dp[u] 为第一次DFS,只考虑 $u$ 的子树内的答案。(考虑深度和即可)

ans[u] 为最终答案,那么有 ans[1] = dp[1]


现在我们要从 $1$ 开始换根。

比如说,我们已知了 $u$ 的答案 $ans[u]$,我们就可以理解成:整棵树,以 $u$ 作为root的答案已经求出来了,怎么求出 $to$ 的答案?

img

换根的过程是一个旋转的过程。我们把 $to$ 的子树向上旋转,将 $to$ 外面的部分($u$ 和其他的子树)向下旋转。

则,向上旋转的部分,对于答案贡献了 -sz[to](因为深度减少了),而向下旋转的部分,对于答案贡献了 (n-sz[to])

所以,$ans[to] = ans[u] - sz[to] + (n - sz[to]);$

代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;

struct Edge {
    int to, nxt;
} edges[maxn<<1];
int n, head[maxn], ecnt = 1;

void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

ll sz[maxn], dp[maxn];
void dfs1(int u, int p) {
    sz[u] = 1;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        dfs1(to, u);
        sz[u] += sz[to];
        dp[u] += dp[to] + sz[to];
    }
}

ll ans[maxn];
void dfs2(int u, int p) {
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        ans[to] = ans[u] - sz[to] + ((ll)n - sz[to]);
        dfs2(to, u);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n-1; i++) {
        int u,v; cin >> u >> v;
        addEdge(u,v); addEdge(v,u);
    }
    dfs1(1, 0);
    ans[1] = dp[1];
    dfs2(1, 0);

    ll maxans = 0, idx = 0;
    for (int i = 1; i <= n; i++) {
        if (ans[i] > maxans) {
            maxans = ans[i];
            idx = i;
        }
    }
    cout << idx << endl;
}

例2 CF1324F Maximum White Subtree

题意

给定 $n$ 个节点的树,每个节点有一个值 $1$ 或者 $-1$。

对于每一个节点 $i$,求 $i$ 所在的连通块中,最大的节点权值和?

其中,$2 \leq n \leq 2 \times 10^5$

题解

首先固定 $1$ 为 root,进行一次DFS。

这样可以求出一个 dp[u]:代表以 $1$ 为root时,每个节点仅考虑其subtree,得到的最大值。

在第一次DFS的过程中,再维护一个数组 bool used[],其中 used[u] = 1 代表 $u$ 的parent $p$ 的答案用到了 $u$ 的这个subtree。


然后进行第二次DFS,计算出最终答案 ans[]

首先有,ans[1] = dp[1]

当我们在 dfs2(u) 时,在求一个child to 的答案 ans[to] 时,我们有两种选择:

  1. to 不使用外面的节点:$ans[to] = \max(ans[to], dp[to])$

  2. to 使用外面的节点:分两种情况讨论

    1. 如果 to 已经被包含在 $u$ 的答案中了(used[to] = 1),则 $ans[to] = \max(ans[to], ans[u])$
    2. 如果 to 并没有被包含在 $u$ 的答案中,(used[to] = 0),那么 to 的最终答案,就是由 $to$ 的subtree 和 外面节点的合并而来。即 $ans[to] = \max(ans[to], ans[u] + dp[to])$
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;

struct Edge {
    int to, nxt;
} edges[maxn<<1];
int n, head[maxn], ecnt = 1, val[maxn];

void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

int dp[maxn];
bool used[maxn];  // when calculating answer, whether used[u] is taken into consideration
void dfs1(int u, int p) {
    dp[u] = val[u];
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        dfs1(to, u);
        if (dp[to] > 0) dp[u] += dp[to], used[to] = 1;
    }
}

int ans[maxn];
void dfs2(int u, int p) {
    ans[u] = max(ans[u], dp[u]);
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        if (used[to]) ans[to] = max(ans[to], ans[u]);
        else ans[to] = max(ans[to], ans[u] + dp[to]);
        dfs2(to, u);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
        if (val[i] == 0) val[i] = -1;
    }
    for (int i = 1; i <= n-1; i++) {
        int u,v; cin >> u >> v;
        addEdge(u,v); addEdge(v,u);
    }
    fill(ans, ans+maxn, -1e9);
    dfs1(1,0);
    dfs2(1,0);
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";
    cout << endl;
}

例3 洛谷P6419 [COCI2014-2015#1] Kamp

题意

给定 $n$ 个节点的树。经过每条边都需要时间 $w_i$。

有 $K$ 个人,初始在 $K$ 个不同的点,他们要集中在一个点聚会。

聚会结束后,一辆车从聚会点出发(装上所有人),把这 $K$ 个人分别送回去。

求:如果聚会点在 $i$,则将这些人都送回去,所需最少的时间?

输出对于所有 $i = 1$ ~ $n$ 的结果。

其中,$1 \leq K \leq n \leq 5 \times 10^5, 1 \leq w \leq 10^8$。

题解

换根DP首先考虑:如果以 $1$ 作为根,怎么求出 $1$ 的答案?

• 以下,所有初始点我们都打上标记。

令 $sz[u]$ 为:$u$ 的 subtree(以 $1$ 为根的版本)中,标记点的数量。

令 $dp[u]$ 为:从 $u$ 出发,经过 $u$ 的 subtree(以 $1$ 为根的版本) 所有标记点再回到 $u$,所需的最少时间(如果子树内无标记,则为0)。

那么通过第一次DFS,我们可以求出整个dp数组。

if (sz[to])
    dp[u] += dp[to] + 2*w;

有了 $dp[1]$,我们还需要一个 $d[u]$,代表以 $u$ 为根的子树(以 $1$ 为根的版本)最长的链的长度

同时我们再记录 $f[u]$:代表以u为根,包含了最长链的直接child $to$ 的编号。

最后 $1$ 对应的答案是:$dp[1] - d[1]$。(因为送到最长链,就不用再回到 $1$ 了)。


现在问题是,已知 $1$ 的答案,我们需要求出其他点的答案。

令 $ans[u]$ 为:从 $u$ 出发,经过整棵树的所有标记点再回到 $u$,所需的最少时间。

易证 $ans[1] = dp[1]$。

然后进行第二次DFS,我们需要改变 $d[u]$ 的意义:此时 $d[u]$ 代表从 $u$ 出发的最长链的长度(以整棵树而言)。

同时,我们再维护一个数组 $s[u]$,代表从 $u$ 出发的第二长链的长度以整棵树而言),并且第二长链必须和最长链 不在同一个子树内(这里的子树指,以 $u$ 为根的判断标准)。

我们在从 $u$ 转移到 $to$ 的时候,就有以下的几种情况:

  1. $to$ 内无标记:

    先从 $to$ 走到 $u$,访问所有的点,再从 $u$ 回到 $to$。

    ans[to] = ans[u] + 2LL * w;
    d[to] = d[u] + w;  // 现在,d[] 表示全局的链
    
  2. $to$ 里面包含了整棵树的所有标记点:

    最终答案就 等于 以 $to$ 为根,subtree的答案。

    ans[to] = dp[to];
    
  3. $to$ 里面包含了标记,外面也包含了标记:

    那么对于整棵树而言,从 $to$ 出发,还是从 $u$ 出发都一样。所以 ans[to] = ans[u]

    但是我们需要更新最长链和次长链。这个时候,我们就要分类讨论 f[u] = to 与否。

    如果 $u$ 原本的最长链就不在 $to$ 的子树内,那么换根以后(旋转),$to$ 的最长链必然是 $to \rightarrow u \rightarrow f[u]$。

    如果 $u$ 原本用到的最长链是 $to$,而旋转后,$to$ 的最长链就有可能用到 $u$ 的其他子树(除了 $to$ 以外的子树),所以我们需要维护次长链 $s[u]$,并且进行比较。

    相应的,换根过程中,我们也要更新次长链 $s[to]$。

     ans[to] = ans[u];
     if (f[u] != to) {  // 原本 to 不是最长,那么现在也必不可能是最长,所以 to 起点的最长链必然继承 u 原来的最长链
         s[to] = d[to];
         d[to] = w + d[u];
         f[to] = u;
     } else {
         if (s[u] + w >= d[to]) {
             s[to] = d[to];
             d[to] = s[u] + w;
             f[to] = u;
         } else if (s[u] + w > s[to]) {
             s[to] = s[u] + w;
         }
     }
    
    
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;

int n, K, head[maxn], ecnt = 1;
bool tag[maxn];
struct Edge {
    int to, nxt, w;
} edges[maxn<<1];

void addEdge(int u, int v, int w) {
    Edge e = {v, head[u], w};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

ll dp[maxn];  // dp[u]: 从u出发,只考虑其subtree中有标记的点,再回到u,得到的答案(如果子树内无标记,则为0)
ll ans[maxn];  // 从u出发,送完所有人,再回到u得到的答案
ll d[maxn];  // d[u]: 以u为根的子树内,最长的链的长度
ll s[maxn];  // s[u]: 以u为根的子树内,次长的链的长度 (不能和d所在的子树相同)
ll f[maxn];  // f[u]: 以u为根,包含了最深的有标记节点的to编号
int sz[maxn];  // sz[u]: 以u为根的subtree里的标记点数量

void chmax(int u, ll val) {
    if (val > d[u]) {
        s[u] = d[u];
        d[u] = val;
    } else {
        if (val > s[u]) s[u] = val;
    }
}

void dfs1(int u, int p) {
    if (tag[u]) {
        sz[u] = 1;
        d[u] = 0;
        s[u] = -1e15;
    } else {
        d[u] = s[u] = -1e15;
    }
    
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        ll w = edges[e].w;

        dfs1(to, u);
        if (!sz[to]) continue;  // 子树内无标记

        dp[u] += dp[to] + 2LL*w;
        sz[u] += sz[to];

        if (d[to] + w >= d[u]) {
            s[u] = d[u];
            d[u] = d[to] + w;
            f[u] = to;
        } else if (d[to] + w > s[u]) {
            s[u] = d[to] + w;
        }
    }
}

void dfs2(int u, int p) {
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        ll w = edges[e].w;
        if (to == p) continue;
        if (!sz[to]) {  // to 里面没有标记点
            ans[to] = ans[u] + 2LL * w;
            d[to] = d[u] + w;  // 现在,d[] 表示全局的链
        } else if (K - sz[to] == 0) {  // to 里面全是标记点
            ans[to] = dp[to];
            // 无需更新最长/次长链
        } else {  // 里外都有标记
            ans[to] = ans[u];
            if (f[u] != to) {  // 原本 to 不是最长,那么现在也必不可能是最长,所以 to 起点的最长链必然出现在 u 所在的子树里
                s[to] = d[to];
                d[to] = w + d[u];
                f[to] = u;
            } else {
                if (s[u] + w >= d[to]) {
                    s[to] = d[to];
                    d[to] = s[u] + w;
                    f[to] = u;
                } else if (s[u] + w > s[to]) {
                    s[to] = s[u] + w;
                }
            }
        }
        dfs2(to, u);
    }
}

int main() {
    cin >> n >> K;
    for (int i = 1; i <= n-1; i++) {
        int u,v,w; cin >> u >> v >> w;
        addEdge(u,v,w); addEdge(v,u,w);
    }
    for (int i = 1; i <= K; i++) {
        int a; cin >> a;
        tag[a] = 1;
    }
    dfs1(1,0);
    ans[1] = dp[1];
    dfs2(1,0);

    for (int i = 1; i <= n; i++) cout << ans[i] - d[i] << "\n";
}

例4 CF708C Centroids

题意

给定一个 $n$ 个节点的树,定义树的重心 $u$ 为:如果以 $u$ 为根,每个子树的大小都 $\leq \frac{n}{2}$。

现在,对于每个点 $u$,我们需要判断:

以 $u$ 为根时,能否在这棵树内,删去一条边,再添加一条边(不能加入已有的边),使得 $u$ 是重心?

其中,$2 \leq n \leq 4 \times 10^5$

题解

首先,如果一个节点本来就是重心,那么它的答案就是 $1$。

现在考虑,如果一个节点 $u$ 现在不是重心,怎么删边和加边,使得它成为重心?

我们会发现,如果以 $u$ 为根,对于 $u$ 的所有 neighbor $v$,有且仅有一个 $v$,使得 $v$ 所在的 subtree 的大小 $> \frac{n}{2}$, 那么我们就从这个 subtree $S_v$ 中,找到一个更小的subtree $S$,满足:

  1. $S$ 的大小 $\leq \frac{n}{2}$。
  2. $S$ 是 $S_v$ 内,所有满足条件中,最大的subtree。

然后我们把这个 subtree $S$ 断开,然后接到 $u$ 上,然后再判断一下 $u$ 此时是否为重心即可。


我们会发现,如果以 $u$ 为根,这样的 $S$ 其实很容易找到。现在要考虑换根的问题。


对于这道题而言,如果我们仅仅维护一个节点 $u$ 作为根时,subtree的信息,那么换根时会很麻烦。

我们需要额外维护一个信息 out[u],其中 $out[u]$ 就代表:以 $1$ 为根时,$u$ 所在子树 $S_u$ 外面的信息

具体定义:$out[u]$ 代表:以 $1$ 为根时,设 $u$ 的parent为 $p$。然后令 $p$ 为根,除了 $S_u$ 以外的部分,满足大小 $\leq \frac{n}{2}$ 的最大子树。

然后就是 套路 里所说的:

先删去 $to$ 对于 $u$ 的贡献,再将 $u$ 加到 $to$ 上。

void dfs2(int u, int p) {
 
    if (n - sz[u] > n/2) {
        if (n - sz[u] - out[u] > n/2) ok[u] = 0;
    }
 
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
 
        if (n - sz[to] <= n/2) {
            out[to] = n - sz[to];
        } else {
            // 删去 to 对于 u 的贡献(维护最大值,次大值 是常见套路了)
            // 再把 u 加到 to 上去(更新 out[to])
            if (use[u][0] == to) {
                out[to] = max(out[u], dp[u][1]);
            } else {
                out[to] = max(out[u], dp[u][0]);
            }
        }
 
        if (sz[to] > n/2) {
            if (sz[to] - dp[to][0] > n/2) ok[u] = 0;
        }
 
        dfs2(to, u);
    }
}

• 当然注意到上述代码,我们不一定要定义一个 $dp2[]$ 数组。这题的状态转移相对简单,所以直接将两步合成一步就可以了。下一题会用到较复杂的状态转移,此时就需要定义 $dp2[]$ 数组了。

代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5+5; 
 
int sz[maxn], head[maxn], ecnt = 1, dp[maxn][2], out[maxn], use[maxn][2], n;
bool ok[maxn];
struct Edge {
    int to, nxt;
} edges[maxn<<1];
 
void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    edges[ecnt] = e;
    head[u] = ecnt++;
}
 
void dfs1(int u, int p) {
    sz[u] = 1;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
        dfs1(to, u);
        sz[u] += sz[to];
        
        if (sz[to] <= n/2) {
            if (sz[to] > dp[u][0]) {
                dp[u][1] = dp[u][0];
                dp[u][0] = sz[to];
                use[u][0] = to;
            } else if (sz[to] > dp[u][1]) {
                dp[u][1] = sz[to];
                use[u][1] = to;
            }
        } else if (dp[to][0] > dp[u][0]) {
            dp[u][1] = dp[u][0];
            dp[u][0] = dp[to][0];
            use[u][0] = to;
        } else if (dp[to][0] > dp[u][1]) {
            dp[u][1] = dp[to][0];
            use[u][1] = to;
        }
    }
}
 
void dfs2(int u, int p) {
 
    if (n - sz[u] > n/2) {
        if (n - sz[u] - out[u] > n/2) ok[u] = 0;
    }
 
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p) continue;
 
        if (n - sz[to] <= n/2) {
            out[to] = n - sz[to];
        } else {
            if (use[u][0] == to) {
                out[to] = max(out[u], dp[u][1]);
            } else {
                out[to] = max(out[u], dp[u][0]);
            }
        }
 
        if (sz[to] > n/2) {
            if (sz[to] - dp[to][0] > n/2) ok[u] = 0;
        }
 
        dfs2(to, u);
    }
}
 
 
int main() {
    fastio;
    cin >> n;
    for (int i = 1; i <= n-1; i++) {
        int u,v; cin >> u >> v;
        addEdge(u,v); addEdge(v,u);
    }
    fill(ok, ok+maxn, 1);
    dfs1(1, 0);
    dfs2(1, 0);
    for (int i = 1; i <= n; i++) {
        cout << ok[i] << " ";
    }
    cout << endl;
}

例5 洛谷P3647 [APIO2014]连珠线

题意

现在有 $n$ 个珠子。珠子之间用线链接,每个线要么是红色,要么是蓝色。

我们将会从其中一个珠子开始(我们不知道这个珠子是哪个),每次用如下两种方式之一,添加珠子:

  1. 将一个 新的珠子 $w$ 和已经添加的珠子 $v$,用红线连起来。
  2. 将两个已经存在的珠子 $u,v$ 之间相连的红线删掉,然后添加一个 新的珠子 $w$ 使得 $(u,w)$,$(w,v)$ 用蓝线链接。

每条线都具有一个长度,游戏结束后,最终得分为蓝线长度之和。

给定游戏结束的局面(是一棵树),我们已知 珠子和线的连接方式,以及每条线的长度。但是我们不知道线的颜色。

求最大可能的得分?

其中,$1 \leq n \leq 2 \times 10^5$

题解

观察一下会发现,如果 $a,b$ 之间有蓝线,$b,c$ 之间也有蓝线。那么 $b$ 就是一个中间节点。这样的节点满足两个条件:

  1. $b$ 与 $a,c$ 一定是直接的neighbor。
  2. $b$ 只能作为一次中间节点(因为 $b$ 是通过第二种操作添加的新节点)
  3. $a,c$ 不能均为中间节点(因为 $a,c$ 之间,必须以红线相连,然后断开才行。这说明 $a,c$ 其中一个必须是通过第一种操作,得到的新珠子)

那么,在最终形成的树中,对于蓝线,有以下两种可能:

第一种情况:grandparent, parent, child

img

第二种情况:parent, child1, child2

img

我们发现第二种情况很复杂,因为我们需要分类讨论 $a,c$ 是否本身为中间节点。

但是第一种情况,就比较好处理。我们只要加一个限定条件:

如果 $b$ 是中间节点(用 $1$ 来标记),那么它用蓝线相连的child $c$,就不能是中间节点(用 $0$ 来标记)。


等等,有两个疑问:

  1. 为什么我们限定的是蓝线相连的 child $c$?为什么不是parent $a$ ?
  2. 那如果第二种情况的那种出现了,怎么办?

这些问题都可以通过 固定 树的根来解决。

我们可以发现,如果我们设定树的根为: 最优解 中,最开始的那个珠子(虽然我们不知道它是哪一个),这些问题就都解决了。(比如第二个问题,我们可以保证这种情况不会出现)。


如上,我们只需要考虑第一种情况。那么,固定 $1$ 为根时,第一次 DFS 中,我们有:

设 $dp[u][0]$ 为:如果 $u$ 不是一个中间节点,那么它所在的subtree $S_u$ 中得到的蓝线长度最大和。

设 $dp[u][1]$ 为:如果 $u$ 一个中间节点,那么它所在的subtree $S_u$ 中得到的蓝线长度最大和。

状态转移方程:

$$dp[u][0] = \sum\limits_{to} \max(w + dp[to][1], dp[to][0])$$

对于 $dp[u][1]$,因为它只能选择一个 child。它选择的那个child $v$,对它的贡献是 $w_{u,v} + dp[v][0]$,其他的child $to$ 的贡献都是 $\max(w + dp[to][1], dp[to][0])$。

所以只要把这个 $v$ 的贡献减去,再加上新贡献就可以了。

$$dp[u][1] = dp[u][0] + \max\limits_v \{ w+dp[v][0] - \max(w+dp[v][1], dp[v][0])\}$$


以 $1$ 为根的情况有了,现在考虑一下换根?

由换根套路,首先将 $to$ 对于 $u$ 的影响删去(基于 $ans[u]$),有:

$$dp2[u][0] = ans[u][0] - \max(w + dp[to][1], dp[to][0])$$

然后,对于 $dp2[u][1]$,我们分类讨论一下 $to$ 是否为 $u$ 的最佳转移点(也就是说,$ans[u][1]$ 是否用到了 $to$,作为最大值)。

$$dp2[u][1] = \begin{cases} ans[u][1] - maxval[u][0] + maxval[u][1] & \text{If to 是 u 的最佳转移点} \\
ans[u][1] & \text{Otherwise} \end{cases}$$

然后,再基于 $dp[to]$ 的基础上,将 $dp2[u]$ 作为 child 给 $to$ 的影响加到 $to$ 上即可。

最后,答案就是 $\max\limits_u \{ans[u][0]\}$。(因为 $ans[u][1]$ 并没有意义,$u$ 作为根的时候是没有parent的)。

代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;

struct Edge {
    int to, w, nxt;
} edges[maxn<<1];
int head[maxn], ecnt = 1, n, dp[maxn][2], dp2[maxn][2], ans[maxn][2];  // dp: 以 1 为根, dp2: 换根后, ans: 最终答案
int use[maxn][2], maxval[maxn][2];  // use[u]: 转移时,所用的前两大的值,对应的两个vertex; maxval[u] : 转移时所用的前两大的值

void addEdge(int u, int v, int w) {
    Edge e = {v, w, head[u]};
    edges[ecnt] = e;
    head[u] = ecnt++;
}

void dfs1(int u, int p) {
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to, w = edges[e].w;
        if (to == p) continue;

        dfs1(to, u);

        dp[u][0] += max(w + dp[to][1], dp[to][0]);  // 转移 dp[u][0]

        // 转移 dp[u][1]
        int val = w + dp[to][0] - max(w + dp[to][1], dp[to][0]);
        if (val > maxval[u][0]) {
            maxval[u][1] = maxval[u][0];
            use[u][1] = use[u][0];
            maxval[u][0] = val;
            use[u][0] = to;
        } else if (val > maxval[u][1]) {
            maxval[u][1] = val;
            use[u][1] = to;
        }
    }
    dp[u][1] = dp[u][0] + maxval[u][0];
}

void dfs2(int u, int p) {
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to, w = edges[e].w;
        if (to == p) continue;

        // 删去 to 对于 u 的影响,基于 ans[u],得到 dp2[u]
        dp2[u][0] = ans[u][0] - max(w + dp[to][1], dp[to][0]);
        if (to == use[u][0]) {
            dp2[u][1] = ans[u][1] - maxval[u][0] + maxval[u][1];
        } else {
            dp2[u][1] = ans[u][1];
        }
        dp2[u][1] -= max(w + dp[to][1], dp[to][0]);

        // 将 dp2[u] 作为 child,重新加给 to(在 dp[to] 的基础上),作为新的 child
        ans[to][0] = dp[to][0] + max(w + dp2[u][1], dp2[u][0]);
        int val = w + dp2[u][0] - max(w + dp2[u][1], dp2[u][0]);
        if (val > maxval[to][0]) {
            maxval[to][1] = maxval[to][0];
            use[to][1] = use[to][0];
            maxval[to][0] = val;
            use[to][0] = u;
        } else if (val > maxval[to][1]) {
            maxval[to][1] = val;
            use[to][1] = u;
        }
        ans[to][1] = ans[to][0] + maxval[to][0];
        dfs2(to, u);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n-1; i++) {
        int u,v,w; cin >> u >> v >> w;
        addEdge(u,v,w); addEdge(v,u,w);
    }
    for (int i = 1; i <= n; i++) maxval[i][0] = maxval[i][1] = -1e9;  // 注意初始化,否则会有问题

    dfs1(1, 0);
    ans[1][0] = dp[1][0], ans[1][1] = dp[1][1];
    dfs2(1, 0);
    int maxans = 0;
    for (int i = 1; i <= n; i++) maxans = max(maxans, ans[i][0]);  // 注意这里是 ans[i][0]
    cout << maxans << endl;
}