1 #include 
     
        2 #include 
      
         3 #include 
       
          4 using namespace std;  5 const int N = 100000;  6   7 /*  8     lca 转RMQ  9  10     询问u和v的lca 11     我们保存树的遍历序列，那么只要在序列中找到第一次出现u和第一次出现v的位置 12     然后RMQ该区间深度最小的那个点就是u和v的lca了 13  14     那么要保存每个点首次出现的位置 15     还要保存遍历序列的dep序列，然后RMQ dep序列得到哪一位置的dep最小 16     然后映射为结点 17 */ 18  19 vector
        
          g[N]; 20 int total; 21 int id[N]; 22 int dep[N]; 23 int ref[N]; 24 int dp[N][30]; 25 int pos[N][30]; 26 void dfs(int u, int fa, int d) 27 { 28     id[u] = ++total; 29     dep[total] = d;//去 30     ref[total] = u; 31     for(int i=0;i
         
           id[v]) 65         swap(u,v); 66     int L = id[u]; 67     int R = id[v]; 68     int k = 0; 69     while(1<<(k+1)<=R-L+1)k++; 70     int a = dp[L][k]; 71     int b = dp[R-(1<