Sadonkorjuu

#include <vector>
#include <utility>
#include <iostream>
#include <cstdint>
#include <queue>
#include <limits>
#include <numeric>
#include <execution>

using namespace std;
using LLi = long long int;

static const LLi MAX_DIST = std::numeric_limits<LLi>::max();


auto solve(const vector<vector<pair<LLi, LLi>>>& edges, const vector<int16_t> node_types, size_t n) -> size_t
{
    priority_queue<pair<LLi, LLi>, std::vector<pair<LLi, LLi>>, std::greater<pair<LLi, LLi>>> distances;

    vector<bool> is_processed(n + 1, false); 
    vector<pair<LLi, LLi>> vertex_attributes(n + 1, make_pair(MAX_DIST, 0));

    for (size_t i = 0; i < node_types.size(); i++) {
        int16_t curr = node_types[i];
        if (curr == 0) {
            vertex_attributes[i] = make_pair(0, i);
            distances.push(vertex_attributes[i]);
            is_processed[i] = true;
        }
    }

    
    auto Relax = [&vertex_attributes]( const pair<LLi, LLi>& curr, const LLi a_neighbour, int32_t weight ) -> void
    {
        if ( curr.first + weight < vertex_attributes[a_neighbour].first )  {
            vertex_attributes[a_neighbour].first = curr.first + weight;
            vertex_attributes[a_neighbour].second = curr.second;
        }
    };


    while ( !(distances.empty()) ) {
        const pair<LLi, LLi> curr = distances.top();
        distances.pop();

        for (const pair<size_t, size_t> a_node : edges[curr.second]) {
            if ( !is_processed[a_node.second] && (node_types[a_node.second] == 1) ) {
                Relax(curr, a_node.second, a_node.first);
                distances.emplace( vertex_attributes[a_node.second].first, a_node.second );
            }
        }

        is_processed[curr.second] = true;
    }

    return transform_reduce(execution::par, vertex_attributes.begin(), vertex_attributes.end(), size_t(0), 
        [](size_t total, const size_t& curr) -> size_t
        {
            return total + curr;
        },
        [](const pair<LLi, LLi>& curr) -> size_t
        {
            return curr.first;
        }
    );
}



int main()
{
    size_t n = 0;
    
    cin >> n;

    vector<int16_t> node_types(n + 1);
    vector<vector<pair<LLi, LLi>>> edges(n + 1);

    for (size_t i = 1; i <= n; i++) {
        cin >> node_types[i];
    }


    int32_t a = 0;
    int32_t b = 0;
    int32_t dist = 0;
    for (size_t i = 0; i < n - 1; i++) {
        cin >> a >> b >> dist;
        edges[a].push_back(make_pair(dist, b));
        edges[b].push_back(make_pair(dist, a));
        
    }

    cout << solve(edges, node_types, n) << endl;

    return EXIT_SUCCESS;
}

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: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

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