APIO 2014 连珠线

这道题的难点在于完全掌握题意，最开始我以为它的意思是“一个节点最多只能当一个连续两蓝线的中点”，
但实际上这么理解就会出问题，因为它的原始题意说的是只允许插入单个珠子，而“工”字形的构造在这时就会发现不可能出现，因为它意味着一定会有两段珠子的中心直接或间接相连接的这一过程，
其实我一开始过度理解题目了，可以尝试带一点模拟思想去看，就是从根向下不断加珠子，新加进来的珠子有可能是日后的中点，也有可能并不是，而所有的连蓝段也就全是“祖-父-孙”型的了，但是注意到在根不同的情况下，之前不存在的“兄弟”型可能在另一种情况下存在了，所以我们应当对所有节点为根的情况挨个求其最优结果并取最大值，由于它的根与根之间的转移比较好处理，所以可以换根DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll n,f[300000][2],head[300000],cnt=1,ans,lian[300000][2],son[300000][2];
struct edge{
    ll to,next,w;
}e[600000];
void make(ll u,ll v,ll w){
    e[cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt++;
}
void dfs1(ll x,ll fa){
    lian[x][0]=lian[x][1]=-1e18;
    for(int i=head[x];i;i=e[i].next){
        if(e[i].to==fa)continue;
        dfs1(e[i].to,x);
        f[x][0]+=max(f[e[i].to][0],f[e[i].to][1]+e[i].w);
        if(f[e[i].to][0]+e[i].w-max(f[e[i].to][0],f[e[i].to][1]+e[i].w)>lian[x][0]){
            lian[x][1]=lian[x][0];
            lian[x][0]=f[e[i].to][0]+e[i].w-max(f[e[i].to][0],f[e[i].to][1]+e[i].w);
            son[x][1]=son[x][0];
            son[x][0]=e[i].to;
        }
        else if(f[e[i].to][0]+e[i].w-max(f[e[i].to][0],f[e[i].to][1]+e[i].w)>lian[x][1]){
            lian[x][1]=f[e[i].to][0]+e[i].w-max(f[e[i].to][0],f[e[i].to][1]+e[i].w);
            son[x][1]=e[i].to;
        }
    }
    f[x][1]=f[x][0]+lian[x][0];
}
void dfs2(ll x,ll fa){
    ans=max(ans,f[x][0]);
    for(int i=head[x];i;i=e[i].next){
        if(e[i].to==fa)continue;
        ll tmpx[2],tmpt[2],tmps[2],tmpl[2];
        tmpx[0]=f[x][0],tmpx[1]=f[x][1];
        tmpt[0]=f[e[i].to][0],tmpt[1]=f[e[i].to][1];
        tmps[0]=son[e[i].to][0],tmps[1]=son[e[i].to][1];
        tmpl[0]=lian[e[i].to][0],tmpl[1]=lian[e[i].to][1];
        if(e[i].to==son[x][0]){
            f[x][0]-=max(f[e[i].to][0],f[e[i].to][1]+e[i].w);
            f[x][1]=f[x][1]-lian[x][0]+lian[x][1]-max(f[e[i].to][0],f[e[i].to][1]+e[i].w);
        }
        else{
            f[x][0]-=max(f[e[i].to][0],f[e[i].to][1]+e[i].w);
            f[x][1]=f[x][1]-max(f[e[i].to][0],f[e[i].to][1]+e[i].w);
        }
        f[e[i].to][0]+=max(f[x][0],f[x][1]+e[i].w);
        if(f[x][0]+e[i].w-max(f[x][0],f[x][1]+e[i].w)>lian[e[i].to][0]){
            lian[e[i].to][1]=lian[e[i].to][0];
            lian[e[i].to][0]=f[x][0]+e[i].w-max(f[x][0],f[x][1]+e[i].w);
            son[e[i].to][1]=son[e[i].to][0];
            son[e[i].to][0]=x;
        }
        else if(f[x][0]+e[i].w-max(f[x][0],f[x][1]+e[i].w)>lian[e[i].to][1]){
            lian[e[i].to][1]=f[x][0]+e[i].w-max(f[x][0],f[x][1]+e[i].w);
            son[e[i].to][1]=x;
        }
        f[e[i].to][1]=f[e[i].to][0]+lian[e[i].to][0];
        dfs2(e[i].to,x);
        f[x][0]=tmpx[0],f[x][1]=tmpx[1];
        f[e[i].to][0]=tmpt[0],f[e[i].to][1]=tmpt[1];
        son[e[i].to][0]=tmps[0],son[e[i].to][1]=tmps[1];
        lian[e[i].to][0]=tmpl[0],lian[e[i].to][1]=tmpl[1];
    }
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        ll u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        make(u,v,w);
        make(v,u,w);
    }
    dfs1(1,0);
    dfs2(1,0);
    printf("%lld",ans);
    return 0;
}