算法竞赛进阶指南HDU-2856.How far away ？(LCA 最近公共祖先)

刺骨的言语ヽ痛彻心扉 2022-02-04 02:17 191阅读 0赞

# [2856.How far away ?][2856.How far away] #

### Problem Description ###

There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this “How far is it if I want to go from house A to house B”? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path(“simple” means you can’t visit a place twice) between every two houses. Yout task is to answer all these curious people.

### Input ###

First line is a single integer T(T<=10), indicating the number of test cases.  
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.  
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.

### Output ###

For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.

### Sample Input ###

2
    3 2
    1 2 10
    3 1 15
    1 2
    2 3
    
    2 2
    1 2 100
    1 2
    2 1

### Sample Output ###

10
    25
    100
    100

### 最近公共祖先(LCA) ###

给定一棵有根树，若结点z既是节点x的祖先，也是节点y的祖先，则称z是x,y的公共祖先。在x,y的所有公共祖先中，深度最大的一个称为x,y的最近公共祖先，记为LCA(x,y)。  
LCA(x,y)是x到根的路径与y到根的路径的交会点。它也是x与y之间路径上深度最小的节点。

### 树上倍增法 ###

设F\[x\]\[k\]表示x的2k辈祖先，即从x向根节点走2k 步到达的节点。特别地，若该节点不存在，则令F\[x\]\[y\]=0。F\[x\]\[0\]就是x的父节点。即x向上走1步就能到达父节点。除此之外，F\[x\]\[k\] = F\[F\[x\]\[k-1\],\[k-1\]\]。即x的第2k辈祖先是x的父亲的第2k-1辈祖先，就比方儿子的爷爷是儿子的爸爸的爸爸。  
这类似一个动态规划的过程，“阶段”就是节点的深度。因此，可以对树进行广度优先遍历，按照层次顺序，在节点入队之前，计算它在F数组中相应的值。  
以上部分是预处理。时间复杂度为(O(nlogN),之后可以多次对不同的x,y计算LCA，每次询问的时间复杂度为O(logn).  
基于F数组的计算LCA(x,y)分为以下几步:

1.  设d\[x\]表示x的深度。不妨设d\[x\]>=d\[y\] (否则可交换x,y)。
2.  用二进制拆分思想，把x向上调整到与y同一深度。  
    具体来说，就是依次尝试从x向上走k = 2logn,…,21,20步，检查到达的节点是否比y深。在每次检查中，若是，则令x = F\[x\]\[k\]。
3.  若此时x == y，说明已经找到了LCA，LCA就等于y。
4.  否则，接着用二进制拆分思想，把x,y同时向上调整，并保持深度一致且二者不相会。  
    具体来说，就是依次尝试把x,y同时向上走k = 2logn,…,21,20步，在每次尝试中，若F\[x\]\[k\]!=F\[y\]k,则令x = F\[x\]\[k\],y = F\[y\]\[k\]。
5.  此时x,y必定只差一步就相会了，它们的父节点F\[x\]\[0\]就是LCA.

#include <iostream>
    #include <math.h>
    #include <queue>
    #include <math.h>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    const int maxn = 40002;
    int t, m, n, k;
    int tot;
    int ver[2*maxn],edge[2*maxn],nexts[2*maxn];
    int head[2*maxn];
    int d[maxn],f[maxn][20],dist[maxn];
    void add(int x,int y,int z){ 
        ver[++tot] = y;
        nexts[tot] = head[x];
        head[x] = tot;
        edge[tot] = z;
    }
    void bfs(){ 
        queue<int> que;
        que.push(1);
        d[1] = 1;
        while(!que.empty()){ 
            int x = que.front();
            que.pop();
            for(int i = head[x]; i; i = nexts[i]){ 
                int y = ver[i];
                if(d[y]) continue;
                dist[y] = dist[x] + edge[i];
                d[y] = d[x] + 1;
                f[y][0] = x;
                for(int j = 1; j <= k;j++){ 
                    f[y][j] = f[f[y][j-1]][j-1];
                }
                que.push(y);
            }
        }
    }
    int lca(int x, int y){ 
        if(d[x] > d[y]) swap(x,y);
        for(int i = k;i >= 0;i--){ 
            if(d[f[y][i]] >= d[x]) y = f[y][i];
        }
        if(x == y) return x;
        for(int i = k;i >= 0;i--){ 
            if(f[x][i] != f[y][i]){ 
                x = f[x][i];
                y = f[y][i];
            }
        }
        return f[x][0];
    }
    int main(){ 
        /* freopen("test.txt","r",stdin); */
        cin >> t;
        while(t--){ 
            cin >> n >> m;
            k = (int)(log(n) / log(2)) + 1;
            for(int i = 1;i <= n;i++){ 
                head[i] = d[i] = 0;
            }
            int u,v,w;
            for(int i = 1;i < n;i++){ 
                cin >> u >> v >> w;
                add(u,v,w);
                add(v,u,w);
            }
            bfs();
            for(int i = 0;i < m;i++){ 
                int x,y;
                cin >> x >> y;
                cout << dist[x] + dist[y] - 2*dist[lca(x,y)] <<endl;
            }
        }
        return 0;
    }

[2856.How far away]: http://acm.hdu.edu.cn/showproblem.php?pid=2586