Sadonkorjuu

input/code.cpp: In function 'int main()':
input/code.cpp:133:20: warning: 'root' may be used uninitialized [-Wmaybe-uninitialized]
  133 |     root->calc_down();
      |     ~~~~~~~~~~~~~~~^~

#include <algorithm>
#include <cassert>
#include <chrono>
#include <climits>
#include <iostream>
#include <memory>
#include <numeric>
#include <sstream>
#include <thread>
#include <vector>

using ll = long long;

#undef assert
#define assert(x)                                                        \
    do {                                                                 \
        if (!(x)) std::this_thread::sleep_for(std::chrono::seconds(10)); \
    } while (0);

struct City {
    City* left  = nullptr;
    City* right = nullptr;
    ll left_dist;
    ll right_dist;

    bool port;

    ll shortest_down = LLONG_MAX;
    bool has_parent  = false;

    void connect(City& o, ll dist) {
        assert(o.has_parent == false);
        if (!left) {
            left      = &o;
            left_dist = dist;
        } else {
            assert(!right);
            right      = &o;
            right_dist = dist;
        }
        o.has_parent = true;
    }

    void calc_down() {
        if (port) {
            shortest_down = 0;
            if (left) left->calc_down();
            if (right) right->calc_down();
            return;
        }
        ll l = LLONG_MAX;
        ll r = LLONG_MAX;
        if (left) {
            left->calc_down();
            l = left->shortest_down;
        }
        if (right) {
            right->calc_down();
            r = right->shortest_down;
        }
        auto add = [](ll a, ll b) {
            if (a == LLONG_MAX || b == LLONG_MAX) return LLONG_MAX;
            return a + b;
        };
        shortest_down = std::min(add(l, left_dist), add(r, right_dist));
    }

    ll shortest = LLONG_MAX;
    void calc_shortest(ll up_dist, City* p) {
        if (!p) {
            shortest = shortest_down;
        } else if (port) {
            shortest = 0;
        } else {
            auto add = [](ll a, ll b) {
                if (a == LLONG_MAX || b == LLONG_MAX) return LLONG_MAX;
                return a + b;
            };
            ll l     = left ? add(left->shortest_down, left_dist) : LLONG_MAX;
            ll r     = right ? add(right->shortest_down, right_dist) : LLONG_MAX;
            shortest = std::min(std::min(l, r), add(p->shortest, up_dist));
        }
        if (left) left->calc_shortest(left_dist, this);
        if (right) right->calc_shortest(right_dist, this);
    }
};

int main() {
    std::cin.sync_with_stdio(false);
    auto& stream = std::cin;

    //    std::stringstream ss{
    //        R"(6
    //        1 1 0 0 1 1
    //        1 2 20
    //        2 3 30
    //        2 5 50
    //        3 6 60
    //        1 4 10
    //        )"
    //    };
    //    ss.copyfmt(std::cin);
    //    ss.exceptions(ss.badbit | ss.failbit);
    //    auto& stream = ss;

    int n;
    stream >> n;

    std::vector<City> cities;
    cities.reserve(n);
    for (int i = 0; i < n; ++i) {
        //
        int v;
        stream >> v;
        City nw;
        nw.port = v == 0 ? true : false;
        cities.push_back(nw);
    }
    for (int i = 0; i < n - 1; ++i) {
        int a, b, c;
        stream >> a >> b >> c;
        cities[a - 1].connect(cities[b - 1], c);
    }

    City* root;
    for (auto& c : cities) {
        if (c.has_parent == false) {
            root = &c;
            break;
        }
    }
    //    std::cout << root << "\n";
    root->calc_down();
    root->calc_shortest(LLONG_MAX, nullptr);
    //    std::cout << root->shortest_down << "\n";
    ll sum = 0;
    for (auto& c : cities) {
        //        std::cout << c.shortest << "\n";
        sum += c.shortest;
    }
    std::cout << sum << "\n";
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 1, 2

Verdict: ACCEPTED

Test 16

Group: 1, 2

Verdict: ACCEPTED

Test 17

Group: 1, 2

Verdict: ACCEPTED

Test 18

Group: 1, 2

Verdict: ACCEPTED

Test 19

Group: 1, 2

Verdict: ACCEPTED

Test 20

Group: 1, 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 1, 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 1, 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 1, 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: ACCEPTED

Test 30

Group: 1, 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: ACCEPTED