thesmartguy97

Untitled

Mar 13th, 2019
45
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cassert>
  5. #define FOR(i, k, n) for(int i = k ; i < n ; i++)
  6. typedef long long int lld  ;
  7.  
  8. // CODE FROM HERE
  9. const int MAX = 11111 ;
  10. lld mod = 1000000007 ;
  11. std::vector <std::vector <lld>> edges(MAX) ;
  12. lld n ;
  13.  
  14. std::vector <lld> ans ;
  15.  
  16. void getEdgeDistances(lld v, lld dis){
  17.     ans.push_back(dis) ;
  18.     assert(ans.size() <= n) ;
  19.  
  20.     for(auto itr : edges[v]){
  21.         getEdgeDistances(itr, (dis + 1)) ;
  22.     }
  23.     return ;
  24. }
  25.  
  26. lld moduloExpo(lld x, lld y){ // x^y
  27.     lld res = 1 ;
  28.     while(y){
  29.         if(y&1)
  30.             res = (lld)(res*x)%mod ;
  31.         x = (lld)(x*x)%mod ;
  32.         y >>= 1ll ;
  33.     }
  34.     return res%mod ;
  35. }
  36.  
  37. int main(){
  38.     lld t, u, q, a, b, v ;
  39.     std::cin >> t ;
  40.  
  41.     while(t--){
  42.         ans.clear() ;
  43.         std::cin >> n >> q ;
  44.  
  45.         FOR(i, 0, n + 20){
  46.             edges[i].clear() ;
  47.         }
  48.  
  49.         FOR(i, 0, n - 1){
  50.             std::cin >> u >> v ;
  51.  
  52.             edges[u].push_back(v) ;
  53.         }
  54.  
  55.         lld answer = 0, y ;
  56.         FOR(i, 0, q){
  57.             std::cin >> a >> b ;
  58.  
  59.             v = a^answer ;
  60.             y = b^answer ;
  61.  
  62.             ans.clear() ;
  63.  
  64.             getEdgeDistances(v, 0) ;
  65.  
  66.             std::sort(ans.begin(), ans.end()) ;
  67.  
  68.             answer = 0 ;
  69.  
  70.             FOR(i, 0, ans.size()){
  71.                 answer += (lld)(ans[i]*moduloExpo(y, i)) ;
  72.                 answer %= mod ;
  73.             }
  74.  
  75.             std::cout << answer << "\n" ;
  76.         }
  77.     }
  78. }
RAW Paste Data