// #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define rep(i, p, k) for(int i(p); i < k; ++i) typedef long long int ll; typedef long double ld; template <typename T = int> inline T in() { T x; std::cin >> x; return x; } constexpr int maxn = 2e5 + 3; std::vector <std::pair <int, int>> graf[maxn]; void kra(int a, int b) { int c(in()); graf[a].emplace_back(b, c); graf[b].emplace_back(a, c); } constexpr ll mi = -1e18; std::map<std::tuple<int, int, int>, ll> back; std::map<std::tuple<int, int, int>, bool> byl; ll odp(int w, int o, int m) { if(byl[{w, o, m}])return back[{w, o, m}]; //std::cerr << w<<' '<<o<<" ["<<m<<"]: ENTER\n"; int sc(graf[w].size()); int size(sc * 2 + 3); std::vector <std::vector <std::array<ll, 2>>> wek{std::vector<std::array<ll, 2>>(size, {mi, mi})}; wek.back()[sc][0] = 0; for(auto i: graf[w])if(i.first != o) { ll rek[5]; rep(j, 0, 5)rek[j] = odp(i.first, w, j); rep(j, 1, 5)rek[j] += i.second; wek.push_back(std::vector<std::array<ll, 2>>(size, {mi, mi})); const auto& o(wek[wek.size() - 2]); auto& d(wek[wek.size() - 1]); rep(i, 0, size)rep(j, 0, 2) { d[i][j] = std::max(d[i][j], o[i][j] + std::max(rek[0], rek[4])); d[i][!j] = std::max(d[i][!j], o[i][j] + rek[2]); if(i > 0)d[i-1][j] = std::max(d[i-1][j], o[i][j] + rek[1]); if(i < o.size() - 1)d[i+1][j] = std::max(d[i+1][j], o[i][j] + rek[3]); } } ll wyn; if(m == 0)wyn = wek.back()[sc][0]; if(m == 1)wyn = wek.back()[sc][0]; if(m == 2)wyn = wek.back()[sc-1][0]; if(m == 3)wyn = wek.back()[sc][1]; if(m == 4)wyn = wek.back()[sc+1][0]; byl[{w, o, m}] = 1; back[{w, o, m}] = wyn; //std::cerr << w <<' '<<o<<" ["<<m<<"]: "<<wyn<<'\n'; return wyn; } int main() { std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(0); int n(in()); rep(i, 1, n)kra(in(), in()); std::cout << odp(1, 1, 0)<<'\n'; return 0; }
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 | // #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define rep(i, p, k) for(int i(p); i < k; ++i) typedef long long int ll; typedef long double ld; template <typename T = int> inline T in() { T x; std::cin >> x; return x; } constexpr int maxn = 2e5 + 3; std::vector <std::pair <int, int>> graf[maxn]; void kra(int a, int b) { int c(in()); graf[a].emplace_back(b, c); graf[b].emplace_back(a, c); } constexpr ll mi = -1e18; std::map<std::tuple<int, int, int>, ll> back; std::map<std::tuple<int, int, int>, bool> byl; ll odp(int w, int o, int m) { if(byl[{w, o, m}])return back[{w, o, m}]; //std::cerr << w<<' '<<o<<" ["<<m<<"]: ENTER\n"; int sc(graf[w].size()); int size(sc * 2 + 3); std::vector <std::vector <std::array<ll, 2>>> wek{std::vector<std::array<ll, 2>>(size, {mi, mi})}; wek.back()[sc][0] = 0; for(auto i: graf[w])if(i.first != o) { ll rek[5]; rep(j, 0, 5)rek[j] = odp(i.first, w, j); rep(j, 1, 5)rek[j] += i.second; wek.push_back(std::vector<std::array<ll, 2>>(size, {mi, mi})); const auto& o(wek[wek.size() - 2]); auto& d(wek[wek.size() - 1]); rep(i, 0, size)rep(j, 0, 2) { d[i][j] = std::max(d[i][j], o[i][j] + std::max(rek[0], rek[4])); d[i][!j] = std::max(d[i][!j], o[i][j] + rek[2]); if(i > 0)d[i-1][j] = std::max(d[i-1][j], o[i][j] + rek[1]); if(i < o.size() - 1)d[i+1][j] = std::max(d[i+1][j], o[i][j] + rek[3]); } } ll wyn; if(m == 0)wyn = wek.back()[sc][0]; if(m == 1)wyn = wek.back()[sc][0]; if(m == 2)wyn = wek.back()[sc-1][0]; if(m == 3)wyn = wek.back()[sc][1]; if(m == 4)wyn = wek.back()[sc+1][0]; byl[{w, o, m}] = 1; back[{w, o, m}] = wyn; //std::cerr << w <<' '<<o<<" ["<<m<<"]: "<<wyn<<'\n'; return wyn; } int main() { std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(0); int n(in()); rep(i, 1, n)kra(in(), in()); std::cout << odp(1, 1, 0)<<'\n'; return 0; } |