[伯俊]#15991 MooTube(Silver)

質問する

農夫のジョンは残りの時間にMoTubeというビデオ共有サービスを作成した.MoTubeでは、農夫のジョンの牛が面白いビデオを共有することができます.牛たちはすでにMooTubeにN(1≦N≦5000)個の番号が1からNのビデオをアップロードした.しかし、ジョンは牛たちが好きな新しいビデオを見つける方法をまだ考えていない.
農夫のジョンは、すべてのMoTubeビデオに「関連ビデオ」リストを作成することにした.これで牛たちは、今見ているビデオとの関連度の高いビデオをお勧めすることができます.
ジョンは2つのビデオ間の距離を測定するために「USADO」を作成した.ジョンはN−1対のビデオを選び,2対のUSADOを直接計算した.そしてジョンはこれらのビデオをネットワーク構造に変え、各ビデオを頂点に表示することにした.また、ジョンは、ビデオの接続構造を、相互に接続されたN−1対のビデオとして表している.より簡単に言えば、ジョンはN−1対のビデオを選択し、あるビデオから別のビデオへのパスが1つ存在しなければならないようにした.ジョンは任意の2対の間のビデオのUSADOをこの経路のすべての接続のUSADOの中で最高値とすることを決定した.
ジョンは、特定のMoTubeビデオに値Kを指定し、このビデオとUSADOがKより大きいすべてのビデオを推奨します.しかしジョンは、あまりにも多くのビデオを推薦すると牛の仕事を妨げるのではないかと心配しています.だから彼はKを適当な値にしたいと思っています.農夫のジョンはあなたがあるK値についての推薦ビデオの個数についていくつかの質問に答えることを望んでいます.

入力

入力された最初の行はNとQを与える.(1 ≤ Q ≤ 5,000)
次のN-1行では、農夫のジョンが自分で量った2つのビデオペアのUSADO 1行1行です.各行は、3つの整数pi、qi、ri(1≦pi、qi≦N、1≦ri≦10000000)p i、q i、r i(1≦p i、qi≦N、1≦ri≦10000000)pi、qi、ri(1≦pi、1≦N、1≦ri≦10000000)を含み、これは、ビデオpip ipiおよびqiq iqiがADUSrir iri相互に接続されていることを意味する.
次のQの問題は農夫のジョンのQの問題です.各行は、2つの整数kiおよびvi(1≦ki≦10000000、1≦vi≦N)k iおよびv i(1≦k i≦10000000、1≦v i≦N)kiおよびvi(1≦ki≦10000000、1≦vi≦N)を含み、これは、ジョンのiの第1の問題がk=kik=k k=kiである場合、ビデオvivを見る牛にどれだけのビデオを推奨するかを意味する.

しゅつりょく

Q個の行を出力します.i行目は農夫ジョンのi番目の質問に対する答えを印刷しなければならない.

入力例1

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

サンプル出力1

3
0
2

に答える

この問題はアルゴリズムで解決できる.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int N;
    static ArrayList<Node>[] map;
    static int[][] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(str[0]);
        int Q = Integer.parseInt(str[1]);
        graph = new int[N+1][N+1];
        map = new ArrayList[N+1];
        for(int i=1; i<=N; i++)
            map[i] = new ArrayList<>();

        for(int i=0; i<N-1; i++) {
            String[] input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int end = Integer.parseInt(input[1]);
            int cost = Integer.parseInt(input[2]);

            map[start].add(new Node(end, cost));
            map[end].add(new Node(start, cost));
        }

        for(int i=1; i<=N; i++)
            bfs(i);

        for(int i=0; i<Q; i++) {
            String[] input = br.readLine().split(" ");
            int K = Integer.parseInt(input[0]);
            int start = Integer.parseInt(input[1]);

            int cnt = 0;

            for(int j=1; j<=N; j++) {
                if(graph[start][j]>=K && start!=j) cnt++;
            }
            sb.append(cnt+"\n");
        }
        System.out.print(sb.toString());
    }

    public static void bfs(int start) {
        Queue<Node> queue = new LinkedList<>();
        boolean[] visited = new boolean[N+1];
        visited[start] = true;
        queue.add(new Node(start, Integer.MAX_VALUE));

        while(!queue.isEmpty()) {
            Node temp = queue.poll();

            for(Node n : map[temp.end]) {
                if(!visited[n.end]) {
                    visited[n.end] = true;
                    int min = Math.min(temp.cost, n.cost);
                    graph[n.end][start] = min;
                    graph[start][n.end] = min;
                    queue.add(new Node(n.end, min));
                }
            }
        }
    }

    public static class Node {
        int end;
        int cost;

        public Node(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }
    }
}