(15681) 트리와 쿼리

https://www.acmicpc.net/problem/15681

단계별로 풀어보기

36단계(트리에서의 동적 계획법) 1번째

 

 

 

트리에서의 동적 계획법은 일반적으로 서브트리의 최적해를 구한 뒤 전체 최적해를 구하는 분할 정복의 방식으로 이루어진다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, r, q;
  
  cin >> n >> r >> q;
  
  vector adj(n+1, vector<int>());
  vector<int> cnt(n+1);
  
  for(int i=1;i<n;i++){
    int u, v;
    
    cin >> u >> v;
    
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  auto dfs= [&](auto self, int now) -> int {
    cnt[now]= 1;
    
    for(int next:adj[now]){
      if(cnt[next])  continue;
      
      cnt[now]+= self(self, next);
    }
    
    return cnt[now];
  };
  
  dfs(dfs, r);
  
  while(q--){
    int u;
    
    cin >> u;
    
    cout << cnt[u] << "\n";
  }
  
  return 0;
}