Advertisement
mickypinata

KOI: Tree

Dec 15th, 2021
619
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 2e5 + 10;
  5.  
  6. vector<int> adj[N];
  7. int pr[N], color[N];
  8.  
  9. void DFS(int u, int p, int prv, int cur){
  10.     color[u] = cur;
  11.     for(int v : adj[u]){
  12.         if(v == p){
  13.             continue;
  14.         }
  15.         if(color[v] == prv){
  16.             DFS(v, u, prv, cur);
  17.         }
  18.     }
  19. }
  20.  
  21. int main(){
  22.  
  23.     int nVertex, Q;
  24.     scanf("%d%d", &nVertex, &Q);
  25.     pr[1] = 0;
  26.     int colorCnt = 0;
  27.     color[1] = ++colorCnt;
  28.     for(int u = 2; u <= nVertex; ++u){
  29.         scanf("%d", &pr[u]);
  30.         adj[u].push_back(pr[u]);
  31.         adj[pr[u]].push_back(u);
  32.         color[u] = colorCnt;
  33.     }
  34.     while(Q--){
  35.         int u, v, cmd;
  36.         scanf("%d%d%d", &u, &v, &cmd);
  37.         int cut = 0;
  38.         if(color[u] == color[v]){
  39.             cout << "YES\n";
  40.             cut = u;
  41.         } else {
  42.             cout << "NO\n";
  43.             cut = v;
  44.         }
  45.         if(cmd == 0 || color[cut] != color[pr[cut]]){
  46.             continue;
  47.         }
  48.         DFS(cut, pr[cut], color[cut], ++colorCnt);
  49.     }
  50.  
  51.     return 0;
  52. }
  53. v
Advertisement
RAW Paste Data Copied
Advertisement