显然dp嘛
首先我们发现，蓝线的连接方式是有限的，具体的，对于每一个节点，其实只有两种可能的连线方式：
第一种：该节点是新来的节点，两个子节点是初始红线的两侧
第二种：该节点是新来的节点，一个子节点和该节点的父节点是红线的两侧
但是，初始是有一个节点的，因此我们考虑进行树形dp时以这个点为根
如果我们确定了这一点之后，我们就会发现第一种连线的方法是不可能的！
因此我们只需考虑第二种转移即可
考虑转移：一个点可以从两个方向转移过来：
如果这个点不是蓝线的中点，那么转移有：
$f[x][0]=sum max(f[to][0],f[to][1]+edge[i].val)$
如果这个点是蓝线的中点，那么转移有：
$f[x][1]=f[x][0]+max(f[to][0]+edge[i].val-max(f[to][0],f[to][1]+edge[i].val)$
这个转移看着很显然，但是问题在于我们起初是随便指定一个点为根的，他不一定合法，我们还需要换根！
如果每次换根都这样dp，时间复杂度就炸飞了
因此我们考虑能否快速维护换根之后的dp值：
首先发现，$f[x][0]$只与每个子节点有关，他需要的是每个子节点的$max(f[to][0],f[to][1]+edge[i].val)$
这个比较好办
但是下面那个就不好办了，因为我们需要分最大值转移过来和非最大值转移过来来讨论
这就比较麻烦了
所以对于每个点，我们维护$f[to][0]+edge[i].val-max(f[to][0],f[to][1]+edge[i].val$这一坨东西的最大值和次大值，分类转移即可
然后我们合并一下状态：设状态$g(i)$表示$f(i)(0)$的状态，忽略掉$f(i)(1)$
因为$f(i)(1)$可以由$g(i)$和最大值直接算出，因此我们不记录$f(i)(1)$也是可以的
那么每次换根的时候，$g(x)$可以直接更新，然后用最大值与次大值分类，更新$g(to)$，然后再更新节点$to$的最大值和次大值
这样就结束了
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> using namespace std; int f[200005][3]; int g[200005]; int n; struct Edge { int nxt; int to; int val; }edge[400005]; int head[200005]; int cnt=1; int ans=0; void add(int l,int r,int w) { edge[cnt].nxt=head[l]; edge[cnt].to=r; edge[cnt].val=w; head[l]=cnt++; } void dfs(int x,int fx) { f[x][1]=f[x][2]=-0x3f3f3f3f; for(int i=head[x];i;i=edge[i].nxt) { int to=edge[i].to; if(to==fx)continue; dfs(to,x); int v=g[to]+edge[i].val-max(g[to],g[to]+f[to][1]+edge[i].val); if(v>f[x][1])f[x][2]=f[x][1],f[x][1]=v; else if(v>f[x][2])f[x][2]=v; g[x]+=max(g[to],g[to]+f[to][1]+edge[i].val); } } void redfs(int x,int fx) { ans=max(ans,g[x]); for(int i=head[x];i;i=edge[i].nxt) { int to=edge[i].to; if(to==fx)continue; int w2=g[to],o1=f[to][1],o2=f[to][2]; int gg=g[x]-max(g[to],g[to]+f[to][1]+edge[i].val); int gf; if(f[x][1]==g[to]+edge[i].val-max(g[to],g[to]+f[to][1]+edge[i].val))gf=f[x][2]; else gf=f[x][1]; g[to]+=max(gg,gg+gf+edge[i].val); gf=gg+edge[i].val-max(gg,gg+gf+edge[i].val); if(gf>f[to][1])f[to][2]=f[to][1],f[to][1]=gf; else if(gf>f[to][2])f[to][2]=gf; redfs(to,x); f[to][1]=o1,f[to][2]=o2; g[to]=w2; } } inline int read() { int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { n=read(); for(int i=1;i<n;i++) { int x=read(),y=read(),z=read(); add(x,y,z),add(y,x,z); } dfs(1,1),redfs(1,1); printf("%d ",ans); return 0; }