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
82
83
84
85
86
87
88
89
90
91
92
93
//Jakub Rozek
//Poborcy podatkowi
//czas: 400n
//pamiec: n

#include "bits/stdc++.h"
using namespace std;

const int N=200005;
const long long INF=1000000000000015;

struct str{
    long long a,b,c,d;
};

vector <pair<int,long long> > tv[N];

str dfs(int a, int b)
{
    if(tv[a].size()==1)
    {
        return {0,-INF,-INF,-INF};
    }

    long long p;
    int q=0,rn;
    pair<int,long long> i;
    int n=min(400,(int)tv[a].size()/2);
    str w,odp;
    long long dp[2][2][2*n+1];

    for(int i=0; i<=2*n; ++i) dp[0][0][i]=-INF;
    for(int i=0; i<=2*n; ++i) dp[0][1][i]=-INF;
    dp[0][0][n]=0;

    for(int it=(int)tv[a].size(); it>0; --it)
    {
        rn=rand()%it;
        i.first=tv[a][rn].first;
        i.second=tv[a][rn].second;
        tv[a][rn].first=tv[a][it-1].first;
        tv[a][rn].second=tv[a][it-1].second;
        
        if(i.first==b) continue;
        w=dfs(i.first,a);
        p=w.d;
        w.d=w.c+i.second;
        w.c=w.b+i.second;
        w.b=w.a+i.second;
        w.a=max(w.a,p+i.second);

        q=1-q;
        dp[q][0][0]=max(w.a+dp[1-q][0][0], max(w.c+dp[1-q][1][0], w.d+dp[1-q][0][1]));
        dp[q][1][0]=max(w.a+dp[1-q][1][0], max(w.c+dp[1-q][0][0], w.d+dp[1-q][1][1]));
        for(int k=1; k<2*n; ++k)
        {
            dp[q][0][k]=max(w.a+dp[1-q][0][k], max(w.c+dp[1-q][1][k], max(w.b+dp[1-q][0][k-1], w.d+dp[1-q][0][k+1])));
            dp[q][1][k]=max(w.a+dp[1-q][1][k], max(w.c+dp[1-q][0][k], max(w.b+dp[1-q][1][k-1], w.d+dp[1-q][1][k+1])));
        }
        dp[q][0][2*n]=max(w.a+dp[1-q][0][2*n], max(w.c+dp[1-q][1][2*n], w.b+dp[1-q][0][2*n-1]));
        dp[q][1][2*n]=max(w.a+dp[1-q][1][2*n], max(w.c+dp[1-q][0][2*n], w.b+dp[1-q][1][2*n-1]));
    }

    odp.a=dp[q][0][n];
    odp.b=dp[q][0][n+1];
    odp.c=dp[q][1][n];
    odp.d=dp[q][0][n-1];
    return odp;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,x,y,z;
    str wynik;

    srand(56235623);

    cin>>n;
    for(int i=1; i<n; ++i)
    {
        cin>>x>>y>>z;
        tv[x].push_back({y,z});
        tv[y].push_back({x,z});
    }
    tv[1].push_back({0,-INF});

    wynik=dfs(1,0);
    cout<<wynik.a<<endl;
    return 0;
}