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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#include <iostream>
#include <vector>
// #include "../../simple-console-debug/debug.h"
using namespace std;

struct Edge {
    int t, w;
    bool *used;
};

// namespace deb{
//     ostream& operator<<(ostream& os, const Edge& e){
//         return os << "(" << e.t << ", " << e.w << ")";
//     }
// };

int n;
vector<vector<Edge>>G;
vector<int>Degs;
long long current_result = 0, best_result = 0;

void R();

void segment_find(int v, int left) {
    // deb::Indent ind;
    // cerr << ind.head << "SF(" << v << ")" << endl;
    if (left == 0)
        R();
    else {
        for (Edge &e : G[v]) {
            // cerr << ind << "try " << e.t << endl;
            if (!*e.used) {
                *e.used = true;
                current_result += e.w;
                Degs[v]--;
                Degs[e.t]--;
                segment_find(e.t, left-1);
                Degs[e.t]++;
                Degs[v]++;
                current_result -= e.w;
                *e.used = false;
            }
        }
    }
}

void R() {
    // deb::Indent ind;
    best_result = max(best_result, current_result);

    //find leaf
    int leaf = -1;
    for (int i = 1; i <= n; i++)
        if (Degs[i] == 1) {
            leaf = i;
            break;
        }
    // cerr << ind.head << "R leaf=" << leaf << endl;
    if (leaf == -1)
        return;

    //case 1 - leaf used
    segment_find(leaf, 4);

    //case 2 - leaf not used
    for (Edge &e : G[leaf])
        if (!*e.used) {
            Degs[leaf] = 0;
            Degs[e.t]--;
            *e.used = true;
            R();
            *e.used = false;
            Degs[e.t]++;
            Degs[leaf] = 1;
        } 
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    bool *usedTab = new bool[n-1];
    fill(usedTab, usedTab+n-1, false);
    G.resize(n+1);
    Degs.resize(n+1, 0);
    for(int i=1;i<n;i++){
        int a, b, w;
        cin >> a >> b >> w;
        G[a].push_back(Edge{.t=b, .w=w, .used=usedTab+i-1});
        G[b].push_back(Edge{.t=a, .w=w, .used=usedTab+i-1});
        Degs[a]++;
        Degs[b]++;
    }

    // for(int i=1;i<=n;i++)
    //     cerr << "Neis[" << i << "] = " << deb::Container(G[i]) << endl;

    R();
    cout << best_result << endl;

    delete[] usedTab;
    return 0;
}