Advertisement
YEZAELP

CUBE-186: XOR tree

Aug 13th, 2020
105
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. using pii = pair<int,int>;
  5. vector <pii> g[100001];
  6. int XOR[100001];
  7. bool visited[100001];
  8.  
  9. int main(){
  10.  
  11.     int n,m;
  12.     scanf("%d%d",&n,&m);
  13.  
  14.     for(int i=1;i<=n-1;i++){
  15.         int u,v,w;
  16.         scanf("%d%d%d",&u,&v,&w);
  17.         g[u].push_back({v,w});
  18.         g[v].push_back({u,w});
  19.     }
  20.  
  21.     queue <pii> q;
  22.     q.push({1,0});
  23.     XOR[1] = 0;
  24.  
  25.     while(q.size() > 0){
  26.         int u,d;
  27.         u = q.front().first;
  28.         d = q.front().second;
  29.         q.pop();
  30.  
  31.         if(visited[u]) continue;
  32.         visited[u] = true;
  33.  
  34.         for(auto vw:g[u]){
  35.             int v,w;
  36.             v = vw.first;
  37.             w = vw.second;
  38.             if(!visited[v]){
  39.                 XOR[v] = w^d;
  40.                 q.push({v,w^d});
  41.             }
  42.         }
  43.     }
  44.  
  45.     for(int i=1;i<=m;i++){
  46.         int u,v;
  47.         scanf("%d%d",&u,&v);
  48.         printf("%d\n",XOR[u]^XOR[v]);
  49.     }
  50.  
  51.     return 0;
  52. }
  53.  
Advertisement
RAW Paste Data Copied
Advertisement