이번 문제는 BFS를 통한 그래프 탐색으로 해결하였다. 문제를 이해하는데 조금 오래 걸렸던 것 같다.

• 매 사이클마다 방문한 영상인지 체크하기 위한 visited 배열을 선언한다.
• 영상은 vector 배열로 선언하여 각 영상에서 추천되는 영상을 저장한다.
• 영상 간의 연결은 양방향이므로 양방향으로 저장해준다.
• 영상 v와 연결된 영상들과 그에 해당하는 k 값을 확인한기 위해 BFS 방식을 활용한다.
• visited가 false인 영상들 중에서 curcost가 k보다 크거나 같은 영상이 있다면 visited를 true로 저장해주고 cnt를 증가시킨다. 이는 추천되는 영상이므로 결과값을 증가시키는 과정이다.

정리하면, 영상 v와 연결된 모든 영상들과의 r값을 확인하고 해당 next의 r값이 k값보다 크거나 같으면 cnt를 증가시킨다. 중복 확인을 방지하기 위해 visited배열을 사용하고, next를 queue에 넣어 next에 대한 위 과정을 반복한다. (queue가 비어있을 때까지 반복하므로 영상 vector의 끝까지 확인하는 셈이다.)

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define MAX 5001
using namespace std;

int n, q;
vector<pair<int, int>> video[MAX];
int k, v;
bool visited[MAX]={false, };

void Input(){
    cin>>n>>q;
    for(int i=0; i<n-1; i++){
        int a,b,c;
        cin>>a>>b>>c;
        video[a].push_back({b,c});
        video[b].push_back({a,c});
    }
}

void InputQ(){
    cin>>k>>v;
}

void BFS(int cost, int cur){
    memset(visited, false, sizeof(visited));
    queue<int> Q;
    int cnt=0;
    visited[cur]=true;
    Q.push(cur);
    while(!Q.empty()){
        int now=Q.front();
        Q.pop();
        for(int i=0; i<video[now].size(); i++){
            int next=video[now][i].first;
            int curcost=video[now][i].second;
            if(visited[next])
                continue;
            if(curcost>=k){
                cnt++;
                visited[next]=true;
                Q.push(next);
            }
        }
    }
    cout<<cnt<<endl;
}

void Solution(){
    Input();
    for(int i=0; i<q; i++){
        InputQ();
        BFS(k, v);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Solution();
    return 0;
}