题目分析
考虑第一颗珠子（根）是谁，那么状态显然是f(x,0/1)，表示x是通过1操作加入的还是通过2操作加入的。如果是通过2操作加入的，那么边(x,father(x))和边(x,son(x))应该是蓝色的。 由此我们可以得到一个枚举根的
O(n2)
O
(
n
2
)
dp: (y指的是x的儿子们,w指的是边的长度）
f(x,0)=∑max(f(y,0),f(y,1)+w(x,y))
f
(
x
,
0
)
=
∑
m
a
x
(
f
(
y
,
0
)
,
f
(
y
,
1
)
+
w
(
x
,
y
)
)
f(x,1)=f(x,0)+max(f(y,0)+w(x,y)−max(f(y,0),f(y,0)+w(x,y)))
f
(
x
,
1
)
=
f
(
x
,
0
)
+
m
a
x
(
f
(
y
,
0
)
+
w
(
x
,
y
)
−
m
a
x
(
f
(
y
,
0
)
,
f
(
y
,
0
)
+
w
(
x
,
y
)
)
)
考虑到我们可以通过两次dfs来完成
O(1)
O
(
1
)
移根，所以能够优化一维复杂度（详情参见树上每个点到离其最远点距离-dp做法），只用在记
f(y,0)+w(x,y)−max(f(y,0),f(y,0)+w(x,y))
f
(
y
,
0
)
+
w
(
x
,
y
)
−
m
a
x
(
f
(
y
,
0
)
,
f
(
y
,
0
)
+
w
(
x
,
y
)
)
最大值的同时记录一下这个的次大值，然后从父亲x到儿子y完成转移时，先减去y子树对f(x)造成的贡献，然后用类似的转移方法，只是当f(y,1)后面那一截取最大值时，若那个儿子恰好对应的是y，则只能取次大值进行dp。
代码
#include<bits/stdc++.h>
using namespace std;
int read() {
int q=
0;
char ch=
' ';
while(ch<
'0'||ch>
'9') ch=getchar();
while(ch>=
'0'&&ch<=
'9') q=q*
10+ch-
'0',ch=getchar();
return q;
}
#define RI register int
const int N=
200005,inf=
0x3f3f3f3f;
int n,tot,ans;
int h[N],ne[N<<
1],to[N<<
1],w[N<<
1];
int f[N],mx1[N],mx2[N],bj[N];
void add(
int x,
int y,
int z) {to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
void dfs1(
int x,
int las) {
mx1[x]=mx2[x]=-inf;
for(RI i=h[x];i;i=ne[i]) {
if(to[i]==las)
continue;
dfs1(to[i],x);
RI kl=max(f[to[i]],f[to[i]]+mx1[to[i]]+w[i]);
f[x]+=kl,kl=f[to[i]]+w[i]-kl;
if(kl>=mx1[x]) mx2[x]=mx1[x],mx1[x]=kl,bj[x]=to[i];
else if(kl>mx2[x]) mx2[x]=kl;
}
}
void dfs2(
int x,
int las) {
ans=max(ans,f[x]);
for(RI i=h[x];i;i=ne[i]) {
if(to[i]==las)
continue;
RI y=to[i];
RI kl=max(f[y],f[y]+mx1[y]+w[i]);
RI orzabs=max(f[x]-kl,f[x]-kl+(bj[x]==y?mx2[x]:mx1[x])+w[i]);
f[y]+=orzabs,orzabs=f[x]-kl+w[i]-orzabs;
if(orzabs>=mx1[y]) mx2[y]=mx1[y],mx1[y]=orzabs,bj[y]=x;
else if(orzabs>mx2[y]) mx2[y]=orzabs;
dfs2(y,x);
}
}
int main()
{
RI x,y,z;
n=read();
for(RI i=
1;i<n;++i)
x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
dfs1(
1,
0),dfs2(
1,
0);
printf(
"%d\n",ans);
return 0;
}
