hdu 4547 （LCA 倍增法）-白红宇

hdu 4547 （LCA 倍增法）

阅读量：6654 次

发布时间：2019-06-25

本文共 1358 字，大约阅读时间需要 4 分钟。

中文题就不解释了。

简单LCA，就是求第一个点到LCA的距离，在判断第二个点是不是LCA，不是答案再加一就可。至于求距离的话直接利用倍增法的parent数组拆成二进制复杂度为logn。

代码如下：

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #include 
                 12 #define MP(a, b) make_pair(a, b) 13 #define PB(a) push_back(a) 14 15 using namespace std; 16 17 typedef long long ll; 18 typedef pair
                 
                   pii; 19 typedef pair
                  
                    puu; 20 typedef pair
                   
                     pid; 21 typedef pair
                    
                      pli; 22 23 const int INF = 0x3f3f3f3f; 24 const double eps = 1e-6; 25 const int LEN = 100010; 26 const int LOG_LEN = 22; 27 vector
                     
                       Map[LEN]; 28 map
                      
                        mp; 29 int ind[LEN], n ,m, root, depth[LEN], parent[LOG_LEN][LEN]; 30 31 void dfs(int v, int p, int d){ 32 parent[0][v] = p; 33 depth[v] = d; 34 for(int i=0; i
                       
                        depth[v])swap(u, v); 54 for(int k=0; k
                        
                         > k & 1) v = parent[k][v]; 56 } 57 if(u==v) return u; 58 for(int k=LOG_LEN-1; k>=0; k--){ 59 if(parent[k][u]!=parent[k][v]){ 60 u = parent[k][u]; 61 v = parent[k][v]; 62 } 63 } 64 return parent[0][v]; 65 } 66 67 int solve(int v, int p){ 68 int ret = 0; 69 for(int i=LOG_LEN-1; i>=0; i--) 70 if(parent[i][v]!=-1 && depth[parent[i][v]]>=depth[p]){ 71 v = parent[i][v]; 72 ret+=(1<