Description

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

Input

第一行是一个正整数$n$，表示珠子的个数，珠子编号为$1$到$n$。
接下来$n-1$行，每行三个正整数$a_{i},b_{i}(1 \le a_{i} \le 10000)$，表示有一条长度为$c_{i}$的线连接了珠子$a_{i}$和珠子$b_{i}$。

Output

输出一个整数，为游戏的最大得分。

Sample Input

5
1 2
1 3 4 0
1 4 1 5
1 5 2 0

Sample Output

60

HINT

数据范围满足$1 \le n \le 200000$。

这题我开始YY树形dpYY了很久，都被自己拍死了，后来是hmr大神（跪烂）告诉了结论的。
对于某种合法的红蓝线分布情况，一定满足蓝线分布在$son_{i},i,father_{i}$之间。
于是$O(n^{2})$dp就出来了。每次换根进行dp即可。状态$f_{i,1}$表示以$i$为根的子树，$i$是蓝线的终点所能得到的最大收益；相反$f_{i,0}$表示以$i$为根的子树，$i$不是蓝线的中点所能够得到的最大收益。
令$cost_{i}$表示$i$与$father_{i}$所连的边的权值大小，那么就有转移$$f_{i,0}=\sum_{j \in son_{i}}max(f_{j,0},f_{j,1}+cost_{j})$$

\[f_{i,1}=f_{i,0}+max(-max(f_{j,0},f_{j,1}+cost_{j})+f_{j,0}+cost_{j})\;(j \in son_{i}) \]

正解就是只进行一遍dp，每次$O(1)$进行换根转移。
我们在第一次dp的时候，记录一下$dp_{i,j,0}$和$dp_{i,j,1}$的值，表示$i$不考虑$j$这个儿子的$f_{i,0/1}$（$dp{i,j,1}$的用$-max(f_{j,0},f_{j,1}+cost_{j})+f_{j,0}+cost_{j})\;(j \in son_{i})$的最大值和次大值维护即可）。
每次换根从父亲换到儿子，只会修改两个点的$f$值，将这两个点用$dp$再转移一遍即可。

#include<vector>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
using namespace std;

#define inf (1<<29)
#define maxn (500010)
int n,side[maxn],toit[maxn*2],next[maxn*2],len[maxn],f[maxn][2],cnt,ans,father[maxn],cost[maxn];
vector <int> son[maxn],dp[maxn][2],best[maxn];

inline void add(int a,int b,int c) { next[++cnt] = side[a]; side[a] = cnt; toit[cnt] = b; len[cnt] = c; }
inline void ins(int a,int b,int c) { add(a,b,c); add(b,a,c); }

inline void update(int &a,int b) { if (b < 0) return; if (b > a) a = b; }

inline void dfs(int now)
{
	f[now][1] = -inf; f[now][0] = 0;
	int fb = -inf,sb = -inf;
	for (int i = side[now];i;i = next[i])
	{
		if (toit[i] == father[now]) continue;
		cost[toit[i]] = len[i]; father[toit[i]] = now; dfs(toit[i]);
		f[now][0] += max(f[toit[i]][0],f[toit[i]][1]+len[i]);
		
		if (-max(f[toit[i]][0],f[toit[i]][1]+len[i])+f[toit[i]][0]+len[i]>fb)
			sb = fb,fb = -max(f[toit[i]][0],f[toit[i]][1]+len[i])+f[toit[i]][0]+len[i];
		else if (-max(f[toit[i]][0],f[toit[i]][1]+len[i])+f[toit[i]][0]+len[i] > sb)
			sb = -max(f[toit[i]][0],f[toit[i]][1]+len[i])+f[toit[i]][0]+len[i];
	}
	f[now][1] = f[now][0] + fb;
	for (int i = side[now],tmp,key;i;i = next[i])
	{
		if (toit[i] == father[now]) continue;
		son[now].push_back(toit[i]);
		dp[now][0].push_back(tmp = f[now][0] - max(f[toit[i]][0],f[toit[i]][1]+len[i]));
		if (-max(f[toit[i]][0],f[toit[i]][1]+len[i])+f[toit[i]][0]+len[i] == fb) key = sb; else key = fb;
		dp[now][1].push_back(tmp + key); best[now].push_back(key);
	}
}

inline void work(int now,int id)
{
	f[now][0] = dp[now][0][id];
	f[now][1] = dp[now][1][id];
	if (father[now])
	{
		f[now][0] += max(f[father[now]][0],f[father[now]][1]+cost[now]);
		f[now][1] = f[now][0];
		int key = max(best[now][id],-max(f[father[now]][0],f[father[now]][1]+cost[now])+f[father[now]][0]+cost[now]);
		f[now][1] += key;
	}
	update(ans,f[son[now][id]][0]+max(f[now][0],f[now][1]+cost[son[now][id]]));
}

inline void Dp(int now)
{
	for (int nn = son[now].size(),i = 0;i < nn;++i)
		work(now,i),Dp(son[now][i]);
}

int main()
{
	freopen("3677.in","r",stdin);
	freopen("3677.out","w",stdout);
	scanf("%d",&n);
	for (int i = 1,a,b,c;i < n;++i) scanf("%d %d %d",&a,&b,&c),ins(a,b,c);
	dfs(1); update(ans,f[1][0]);
	Dp(1);	
	printf("%d",ans);
	fclose(stdin); fclose(stdout);
	return 0;
}