LCA入门题集小结

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2586

题目：

How far away ？

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 21500    Accepted Submission(s): 8471

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

 

思路：裸题，套模板即可。

代码实现如下：

#include <cstdio>
#include <vector>
using namespace std;

const int maxn = 4e4 + 7;
int n, m, u, v, k;
int fa[maxn][30], deep[maxn], cost[maxn];

struct edge {
    int v, l;
    edge(int v = 0, int l = 0) : v(v), l(l) {}
};

vector<edge> G[maxn];

void dfs(int u, int d, int p) {
    deep[u] = d;
    fa[u][0] = p;
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].v;
        if(v != p) {
            cost[v] = cost[u] + G[u][i].l;
            dfs(v, d + 1, u);
        }
    }
}

void lca() {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; (1 << j) <= n; j++) {
            fa[i][j] = -1;
        }
    }
    for(int j = 1; (1 << j) <= n; j++) {
        for(int i = 1; i <= n; i++) {
            if(fa[i][j-1] != -1) {
                fa[i][j] = fa[fa[i][j-1]][j-1];
            }
        }
    }
}

int query(int u, int v) {
    if(deep[u] < deep[v]) swap(u, v);
    int k;
    for(k = 0; (1 << (k + 1)) <= deep[u]; k++);
    for(int i = k; i >= 0; i--) {
        if(deep[u] - (1 << i) >= deep[v]) {
            u = fa[u][i];
        }
    }
    if(u == v) return u;
    for(int i = k; i >= 0; i--) {
        if(fa[u][i] != -1 && fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++) {
            G[i].clear();
        }
        for(int i = 1; i < n; i++) {
            scanf("%d%d%d", &u, &v, &k);
            G[u].push_back(edge(v, k));
            G[v].push_back(edge(u, k));
        }
        dfs(1, 0, -1);
        lca();
        while(m--) {
            scanf("%d%d", &u, &v);
            printf("%d
", cost[u] + cost[v] - 2 * cost[query(u, v)]);
        }
    }
    return 0;
}

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2874

题目：

Connections between cities

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13879    Accepted Submission(s): 3159

Problem Description

After World War X, a lot of cities have been seriously damaged, and we need to rebuild those cities. However, some materials needed can only be produced in certain places. So we need to transport these materials from city to city. For most of roads had been totally destroyed during the war, there might be no path between two cities, no circle exists as well.
Now, your task comes. After giving you the condition of the roads, we want to know if there exists a path between any two cities. If the answer is yes, output the shortest path between them.

 

Input

Input consists of multiple problem instances.For each instance, first line contains three integers n, m and c, 2<=n<=10000, 0<=m<10000, 1<=c<=1000000. n represents the number of cities numbered from 1 to n. Following m lines, each line has three integers i, j and k, represent a road between city i and city j, with length k. Last c lines, two integers i, j each line, indicates a query of city i and city j.

 

Output

For each problem instance, one line for each query. If no path between two cities, output “Not connected”, otherwise output the length of the shortest path between them.

 

Sample Input

5 3 2

1 3 2

2 4 3

5 2 3

1 4

4 5

 

Sample Output

Not connected

6 

 

题解链接：https://www.cnblogs.com/Dillonh/p/9135364.html

 

题目链接：http://poj.org/problem?id=1986

题目：

Distance Queries

Time Limit: 2000MS		Memory Limit: 30000K
Total Submissions: 15827		Accepted: 5576
Case Time Limit: 1000MS

Description

Farmer John's cows refused to run in his marathon since he chose a path much too long for their leisurely lifestyle. He therefore wants to find a path of a more reasonable length. The input to this problem consists of the same input as in "Navigation Nightmare",followed by a line containing a single integer K, followed by K "distance queries". Each distance query is a line of input containing two integers, giving the numbers of two farms between which FJ is interested in computing distance (measured in the length of the roads along the path between the two farms). Please answer FJ's distance queries as quickly as possible!

Input

* Lines 1..1+M: Same format as "Navigation Nightmare"

* Line 2+M: A single integer, K. 1 <= K <= 10,000

* Lines 3+M..2+M+K: Each line corresponds to a distance query and contains the indices of two farms.

Output

* Lines 1..K: For each distance query, output on a single line an integer giving the appropriate distance.

Sample Input

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6
1 4
2 6

Sample Output

13
3
36

Hint

Farms 2 and 6 are 20+3+13=36 apart.

 

思路：不要管这傻逼题面，输入就是裸的LCA输入格式，那个字母也不用管，可以使用%*s来读入字母。

代码实现如下：

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int maxn = 1e5 + 7;
int n, m, q, u, v, k;
int fa[maxn][30], deep[maxn], cost[maxn];

struct edge {
    int v, l;
    edge(int v = 0, int l = 0) : v(v), l(l) {}
};

vector<edge> G[maxn];

void dfs(int u, int d, int p) {
    deep[u] = d;
    fa[u][0] = p;
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].v;
        if(v != p) {
            cost[v] = cost[u] + G[u][i].l;
            dfs(v, d + 1, u);
        }
    }
}

void lca() {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; (1 << j) <= n; j++) {
            fa[i][j] = -1;
        }
    }
    for(int j = 1; (1 << j) <= n; j++) {
        for(int i = 1; i <= n; i++) {
            if(fa[i][j-1] != -1) {
                fa[i][j] = fa[fa[i][j-1]][j-1];
            }
        }
    }
}

int query(int u, int v) {
    if(deep[u] < deep[v]) swap(u, v);
    int k;
    for(k = 0; (1 << (1 + k)) <= deep[u]; k++);
    for(int i = k; i >= 0; i--) {
        if(deep[u] - (1 << i) >= deep[v]) {
            u = fa[u][i];
        }
    }
    if(u == v) return u;
    for(int i = k; i >= 0; i--) {
        if(fa[u][i] != -1 && fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

int main() {
    while(~scanf("%d%d", &n, &m)) {
        memset(cost, 0, sizeof(cost));
        for(int i = 0; i <= n; i++) {
            G[i].clear();
        }
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d%*s", &u, &v, &k);
            G[u].push_back(edge(v, k));
            G[v].push_back(edge(u, k));
        }
        dfs(1, 0, -1);
        lca();
        scanf("%d", &q);
        while(q--) {
            scanf("%d%d", &u, &v);
            printf("%d
", cost[u] + cost[v] - 2 * cost[query(u, v)]);
        }
    }
    return 0;
}

题目链接：http://poj.org/problem?id=1330

题目：

Nearest Common Ancestors

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 32969		Accepted: 16750

Description

A rooted tree is a well-known data structure in computer science and engineering. An example is shown below:


In the figure, each node is labeled with an integer from {1, 2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is.

For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest common ancestor of y and z is y.

Write a program that finds the nearest common ancestor of two distinct nodes in a tree.

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are labeled with integers 1, 2,..., N. Each of the next N -1 lines contains a pair of integers that represent an edge --the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N - 1 edges. The last line of each test case contains two distinct integers whose nearest common ancestor is to be computed.

Output

Print exactly one line for each test case. The line should contain the integer that is the nearest common ancestor.

Sample Input

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

Sample Output

4
3


思路：裸的LCA，不过要注意它的节点之间是有向的，所以需要用一个数组来储存入度，以入度为0的节点做根节点。
代码实现如下：

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int maxn = 1e4 + 7;
int t, n, u, v, s;
int deep[maxn], fa[maxn][30], in[maxn];

vector<int> G[maxn];

void dfs(int u, int d, int p) {
    deep[u] = d;
    fa[u][0] = p;
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if(v != p) {
            dfs(v, d + 1, u);
        }
    }
}

void lca() {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; (1 << j) <= n; j++) {
            fa[i][j] = -1;
        }
    }
    for(int j = 1; (1 << j) <= n; j++) {
        for(int i = 1; i <= n; i++) {
            if(fa[i][j-1] != -1) {
                fa[i][j] = fa[fa[i][j-1]][j-1];
            }
        }
    }
}

int query(int u, int v) {
    if(deep[u] < deep[v]) swap(u, v);
    int k;
    for(k = 0; (1 << (1 + k)) <= deep[u]; k++);
    for(int i = k; i >= 0; i--) {
        if(deep[u] - (1 << i) >= deep[v]) {
            u = fa[u][i];
        }
    }
    if(u == v) return u;
    for(int i = k; i >= 0; i--) {
        if(fa[u][i] != -1 && fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 0; i <= n; i++) {
            G[i].clear();
        }
        memset(in, 0, sizeof(in));
        for(int i = 1; i < n; i++) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
            in[v]++;
        }
        for(int i = 1; i <= n; i++) {
            if(in[i] == 0) {
                s = i;
                break;
            }
        }
        dfs(s, 0, -1);
        lca();
        scanf("%d%d", &u, &v);
        printf("%d
", query(u, v));
    }
    return 0;
}

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4547

题目：

CD操作

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 3035    Accepted Submission(s): 848

Problem Description

　　在Windows下我们可以通过cmd运行DOS的部分功能，其中CD是一条很有意思的命令，通过CD操作，我们可以改变当前目录。
　　这里我们简化一下问题，假设只有一个根目录，CD操作也只有两种方式：
　　
　　1. CD 当前目录名...目标目录名 (中间可以包含若干目录，保证目标目录通过绝对路径可达)
　　2. CD .. (返回当前目录的上级目录)
　　
　　现在给出当前目录和一个目标目录，请问最少需要几次CD操作才能将当前目录变成目标目录？

 

Input

输入数据第一行包含一个整数T(T<=20)，表示样例个数；
每个样例首先一行是两个整数N和M(1<=N,M<=100000)，表示有N个目录和M个询问；
接下来N-1行每行两个目录名A B(目录名是只含有数字或字母，长度小于40的字符串)，表示A的父目录是B。
最后M行每行两个目录名A B，表示询问将当前目录从A变成B最少要多少次CD操作。
数据保证合法，一定存在一个根目录，每个目录都能从根目录访问到。

 

Output

请输出每次询问的结果，每个查询的输出占一行。

 

Sample Input

2

3 1

B A

C A

B C

 

3 2

B A

C B

A C

C A

 

Sample Output

2

1

2

 

思路：由于读入是字符串，因此我们需要借助map来将它转换成数字。同时此图也是给定了节点之间的方向，需要借助入度为0的节点来做根节点。看第二组数据和第三组数据我们发现此题的一个trick：从祖宗目录到子目录操作步数只需一步，然后我们可以发现，当所要到达的目录如果是当前目录的祖宗目录时，输出cost[u]-cost[query(u,v)],否则还要+1.

代码实现如下：

#include <map>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 1e5 + 7;
int t, n, m, cnt;
string s1, s2;
int cost[maxn], deep[maxn], fa[maxn][30], in[maxn];

struct edge {
    int v, l;
    edge (int v = 0, int l = 0) : v (v), l (l) {}
};

vector<edge> G[maxn];
map<string, int> mp;

void init() {
    cnt = 0;
    mp.clear();
    memset (in, 0, sizeof (in) );
    memset (cost, 0, sizeof (cost) );
    for (int i = 0; i <= n; i++) {
        G[i].clear();
    }
}

void dfs (int u, int d, int p) {
    deep[u] = d;
    fa[u][0] = p;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].v;
        if (v != p) {
            cost[v] = cost[u] + G[u][i].l;
            dfs (v, d + 1, u);
        }
    }
}

void lca() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; (1 << j) <= n; j++) {
            fa[i][j] = -1;
        }
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i <= n; i++) {
            if (fa[i][j - 1] != -1) {
                fa[i][j] = fa[fa[i][j - 1]][j - 1];
            }
        }
    }
}

int query (int u, int v) {
    if (deep[u] < deep[v])
        swap (u, v);
    int k;
    for (k = 0; (1 << (1 + k) ) <= deep[u]; k++);
    for (int i = k; i >= 0; i--) {
        if (deep[u] - (1 << i) >= deep[v]) {
            u = fa[u][i];
        }
    }
    if (u == v)
        return u;
    for (int i = k; i >= 0; i--) {
        if (fa[u][i] != -1 && fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

int main() {
    ios::sync_with_stdio (false);
    cin.tie (0);
    cin >> t;
    while (t--) {
        cin >> n >> m;
        init();
        for (int i = 1; i < n; i++) {
            cin >> s1 >> s2;
            if(mp.find(s1) == mp.end())
                mp[s1] = ++cnt;
            if(mp.find(s2) == mp.end())
                mp[s2] = ++cnt;
            in[mp[s1]]++;
            G[mp[s1]].push_back (edge (mp[s2], 1) );
            G[mp[s2]].push_back (edge (mp[s1], 1) );
        }
        int s;
        for (int i = 1; i <= n; i++) {
            if (in[i] == 0) {
                s = i;
            }
        }
        dfs (s, 0, -1);
        lca();
        while (m--) {
            cin >> s1 >> s2;
            if(query(mp[s1], mp[s2]) == mp[s2]) {
                cout <<cost[mp[s1]] - cost[mp[s2]] <<endl;
            } else {
                cout << cost[mp[s1]] - cost[query (mp[s1], mp[s2])] + 1 << endl;
            }
        }
    }
    return 0;
}

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3195

题目：

Design the city

---

Time Limit: 1 Second      Memory Limit: 32768 KB

---

Cerror is the mayor of city HangZhou. As you may know, the traffic system of this city is so terrible, that there are traffic jams everywhere. Now, Cerror finds out that the main reason of them is the poor design of the roads distribution, and he want to change this situation.

In order to achieve this project, he divide the city up to N regions which can be viewed as separate points. He thinks that the best design is the one that connect all region with shortest road, and he is asking you to check some of his designs.

Now, he gives you an acyclic graph representing his road design, you need to find out the shortest path to connect some group of three regions.

Input

The input contains multiple test cases! In each case, the first line contian a interger N (1 < N < 50000), indicating the number of regions, which are indexed from 0 to N-1. In each of the following N-1 lines, there are three interger Ai, Bi, Li (1 < Li < 100) indicating there's a road with length Li between region Ai and region Bi. Then an interger Q (1 < Q < 70000), the number of group of regions you need to check. Then in each of the following Q lines, there are three interger Xi, Yi, Zi, indicating the indices of the three regions to be checked.

Process to the end of file.

Output

Q lines for each test case. In each line output an interger indicating the minimum length of path to connect the three regions.

Output a blank line between each test cases.

Sample Input

4
0 1 1
0 2 1
0 3 1
2
1 2 3
0 1 2
5
0 1 1
0 2 1
1 3 1
1 4 1
2
0 1 2
1 0 3

Sample Output

3
2

2
2

思路：将所给的x,y,z分别两两求一次lca，然后除2即可。
代码实现如下：

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int maxn = 5e4 + 7;
int n, q, u, v, k;
int cost[maxn], deep[maxn], fa[maxn][30];

struct edge {
    int v, l;
    edge(int v = 0, int l = 0) : v(v), l(l) {}
};

vector<edge> G[maxn];

void init() {
    memset(cost, 0, sizeof(cost));
    for(int i = 0; i < maxn; i++) {
        G[i].clear();
    }
}

void dfs(int u, int d, int p) {
    deep[u] = d;
    fa[u][0] = p;
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].v;
        if(v != p) {
            cost[v] = cost[u] + G[u][i].l;
            dfs(v, d + 1, u);
        }
    }
}

void lca() {
    for(int i = 0; i < n; i++) {
        for(int j = 1; (1 << j) < n; j++) {
            fa[i][j] = -1;
        }
    }
    for(int j = 1; (1 << j) < n; j++) {
        for(int i = 0; i < n; i++) {
            if(fa[i][j-1] != -1) {
                fa[i][j] = fa[fa[i][j-1]][j-1];
            }
        }
    }
}

int query(int u, int v) {
    if(deep[u] < deep[v]) swap(u, v);
    int k;
    for(k = 0; (1 << k) <= deep[u]; k++);
    for(int i = k; i >= 0; i--) {
        if(deep[u] - (1 << i) >= deep[v]) {
            u = fa[u][i];
        }
    }
    if(u == v) return u;
    for(int i = k; i >= 0; i--) {
        if(fa[u][i] != -1 && fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

int main() {
    int flag = 0;
    while(~scanf("%d", &n)) {
        if(flag) printf("
");
        flag = 1;
        init();
        for(int i = 1; i < n; i++) {
            scanf("%d%d%d", &u, &v, &k);
            G[u].push_back(edge(v, k));
            G[v].push_back(edge(u, k));
        }
        dfs(0, 0, -1);
        lca();
        scanf("%d", &q);
        while(q--) {
            scanf("%d%d%d", &u, &v, &k);
            printf("%d
", (cost[u] + cost[v] - 2 * cost[query(u, v)] + cost[u] + cost[k] - 2 * cost[query(u, k)] + cost[v] + cost[k] - 2 * cost[query(v, k)]) / 2);
        }
    }
    return 0;
}

至此感觉自己的LCA应该算是入门了，深入刷难题暑假再开始，毕竟现在要开始准备期末了，免得上学期专业课满绩点，高代全年级第一，这学期全部挂科然后挨骂Σ( ° △ °|||)︴