Sadonkorjuu

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Solver solver = new Solver();
        System.out.println(solver.Solve());
    }
}


class Solver{

    public long Solve() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        // INPUT
        int cityCount = Integer.parseInt(bufferedReader.readLine());
        String[] cityTypes = bufferedReader.readLine().split(" ");
        City[] cities = new City[cityCount];
        for(int i = 0; i < cityCount; i++){
            cities[i] = new City(i, Integer.parseInt(cityTypes[i]) == 1);
        }
        for(int i = 0; i < cityCount - 1; i++){
            String[] inp = bufferedReader.readLine().split(" ");
            cities[Integer.parseInt(inp[0]) - 1].AddConnection(cities[Integer.parseInt(inp[1]) - 1], Integer.parseInt(inp[2]));
            cities[Integer.parseInt(inp[1]) - 1].AddConnection(cities[Integer.parseInt(inp[0]) - 1], Integer.parseInt(inp[2]));
        }

        // test generator
        /*int cityCount = 200000;
        City[] cities = new City[cityCount];
        Random random = new Random();
        for(int i = 0; i < cityCount; i++){
            cities[i] = new City(i, (random.nextInt(cityCount) < cityCount / 1.5));
        }
        for(int i = 0; i < cityCount - 1; i++){
            int randomIndex;
            do {
                randomIndex = random.nextInt(cityCount);
            }
            while (randomIndex == i);

            String[] inp = {String.valueOf(i), String.valueOf(randomIndex), "1"};
            cities[Integer.parseInt(inp[0])].AddConnection(cities[Integer.parseInt(inp[1])], Integer.parseInt(inp[2]));
            cities[Integer.parseInt(inp[1])].AddConnection(cities[Integer.parseInt(inp[0])], Integer.parseInt(inp[2]));
        }*/
        
        //long start = System.currentTimeMillis();

        // ALG
        Queue<SearchState> q = new LinkedList<>();
        long fieldCount = 0;
        for(int i = 0; i < cityCount; i++){
            if(!cities[i].isField && cities[i].hasFieldConnection){
                List<Integer> visited = new ArrayList<>(1);
                visited.add(i);
                q.add(new SearchState(cities[i], 0, visited));
            }
            else if(cities[i].isField) {
                fieldCount += 1;
            }
        }

        long totalLength = fieldCount * 999999999;
        while (q.size() > 0) {
            SearchState state = q.poll();
            if (state.city.shortestPath < state.totalCost){
                continue;
            }
            for (Connection connection : state.city.connections) {
                if (!connection.destination.isField) { continue; }
                if (state.visited.contains(connection.destination.cityID)) { continue; } 

                int newCost = state.totalCost + connection.cost;
                if (newCost < connection.destination.shortestPath){
                    totalLength -= connection.destination.shortestPath - newCost;
                    connection.destination.shortestPath = newCost;
                } else { continue; }

                state.visited.add(connection.destination.cityID);
                SearchState newState = new SearchState(connection.destination, newCost, new ArrayList<Integer>(state.visited));
                q.add(newState);
            }
        }

        //System.out.println((System.currentTimeMillis() - start) / 1000.0);
        return totalLength;
    }


    class SearchState {
        public City city;
        public int totalCost;
        public List<Integer> visited = new ArrayList<>();

        public SearchState(City city, int totalCost, List<Integer> visited){
            this.city = city;
            this.visited = visited;
            this.totalCost = totalCost;
        }
    }


    class City {
        public int cityID;
        public boolean isField;
        public boolean hasFieldConnection = false;
        public List<Connection> connections;
        public int shortestPath = 999999999;
    
        public City(int cityID, boolean isField){
            this.cityID = cityID;
            this.isField = isField;
            connections = new ArrayList<Connection>();  
        }
    
        public void AddConnection(City destination, int cost) {
            connections.add(new Connection(destination, cost));
            if(destination.isField){
                hasFieldConnection = true;
            }
        }
    }
    
    class Connection {
        public City destination;
        public int cost;
    
        public Connection(City destination, int cost){
            this.destination = destination;
            this.cost = cost;
        }
    }
}

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: TIME LIMIT EXCEEDED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 2

Verdict: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED

Test 24

Group: 1, 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 1, 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 1, 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 1, 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: TIME LIMIT EXCEEDED