LCA专题-白红宇

LCA专题

阅读量：5331 次

发布时间：2019-06-14

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

先上模板~

/*    LCA(倍增法，二分搜索)：rt[i][u](i
     
      > i & 1) {            u = rt[i][u];        }    }    if (u == v) return u;    for (int i=D-1; i>=0; --i)  {        if (rt[i][u] != rt[i][v])   {            u = rt[i][u];            v = rt[i][v];        }    }    return rt[0][u];}void solve(void)    {    DFS (1, -1, 0);    for (int i=1; i

/*    LCA -> RMQ: LCA (u, v) = F[id[u] <= i <= id[v]中dep[i]最小的i];    RMQ预处理复杂度O(nlogn)，每次询问O (1)    (dp[N<<1][D], F[N<<1], dep[N<<1], id[N])*/void DFS(int u, int fa, int d, int &k)  {    id[u] = k;  F[k] = u;   dep[k++] = d;    for (int i=head[u]; ~i; i=edge[i].nex)  {        int v = edge[i].v;        if (v == fa)    continue;        DFS (v, u, d + 1, k);        F[k] = u;   dep[k++] = d;    }}int Min(int i, int j)   {    return dep[i] < dep[j] ? i : j;}void init_RMQ(int k)  {    for (int i=0; i

/*    LCA离线处理，Tarjan算法，复杂度O (N+Q)    对询问次序按深搜时遍历到的节点顺序进行重组，并查集找祖先    ans[i]表示第i个询问的LCA*/void LCA(int u)    {    rt[u] = u;    for (int i=head[u]; ~i; i=edge[i].nex)  {        int v = edge[i].v;        if (rt[v] == -1)    {            LCA (v);            rt[v] = u;        }    }    for (int i=headq[u]; ~i; i=query[i].nex)    {        int v = query[i].v;        if (rt[v] != -1)    {            int lca = Find (v);            ans[query[i].id] = lca;        }    }}

推荐资源：

模版题

/************************************************* Author        :Running_Time* Created Time  :2015/10/5 星期一 15:12:31* File Name     :POJ_1330.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e4 + 10;const int D = 20;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-8;struct Edge { int v, nex;}edge[N<<1];int head[N], in[N], e;int F[N<<1], dep[N<<1], id[N];int dp[N<<1][D];void init(void) { memset (head, -1, sizeof (head)); memset (in, 0, sizeof (in)); e = 0;}int Min(int i, int j) { return dep[i] < dep[j] ? i : j;}void add_edge(int u, int v) { edge[e] = (Edge) {v, head[u]}; head[u] = e++;}void DFS(int u, int fa, int d, int &k) { id[u] = k; F[k] = u; dep[k++] = d; for (int i=head[u]; ~i; i=edge[i].nex) { int v = edge[i].v; if (v == fa) continue; DFS (v, u, d + 1, k); F[k] = u; dep[k++] = d; }}void init_RMQ(int k) { memset (dp, 0, sizeof (dp)); for (int i=0; i

模版题

/************************************************* Author        :Running_Time* Created Time  :2015/10/4 星期日 18:36:06* File Name     :HDOJ_2586.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 4e4 + 10;const int M = 2e2 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-8;struct Edge { int v, nex, len;}edge[N*2];struct Query { int v, nex, len, id;}query[M*2];int head[N], headq[N], rt[N], d[N], ans[M];int n, m, e, q;void init(void) { memset (head, -1, sizeof (head)); memset (headq, -1, sizeof (headq)); memset (rt, -1, sizeof (rt)); e = 0; q = 0;}void add_edge(int u, int v, int len) { edge[e].v = v; edge[e].len = len; edge[e].nex = head[u]; head[u] = e++;}void add_query(int u, int v, int id) { query[q].v = v; query[q].id = id; query[q].nex = headq[u]; headq[u] = q++;}int Find(int x) { return rt[x] == x ? x : rt[x] = Find (rt[x]);}void LCA(int u, int len) { d[u] = len; rt[u] = u; for (int i=head[u]; ~i; i=edge[i].nex) { int v = edge[i].v; if (rt[v] == -1) { LCA (v, len + edge[i].len); rt[v] = u; } } for (int i=headq[u]; ~i; i=query[i].nex) { int v = query[i].v; if (rt[v] != -1) { int lca = Find (v); ans[query[i].id] = d[u] + d[v] - (d[lca] << 1); } }}int main(void) { int T; scanf ("%d", &T); while (T--) { init (); scanf ("%d%d", &n, &m); for (int u, v, len, i=1; i