[UVA][LCA][Tarjan] 12238 - Ants Colony
A group of ants is really proud because they built a magnificent and large colony. However, the enormous size has become a problem, because many ants do not know the path between some parts of the colony. They desperately need your help!
The colony of ants was made as a series of N anthills, connected by tunnels. The ants, obsessive as they are, numbered the anthills sequentially as they built them. The first anthill, numbered 0, did not require any tunnel, but for each of the subsequent anthills, 1 through N - 1, the ants also built a single tunnel that connected the new anthill to one of the existing anthills. Of course, this tunnel was enough to allow any ant to go to any previously built anthill, possibly passing through other anthills in its path, so they did not bother making extra tunnels and continued building more anthills.
Your job is, given the structure of the colony and a set of queries, calculate for each query the shortest path between pairs of anthills. The length of a path is the sum of the lengths of all tunnels that need to be traveled.
Input
Each test case is given using several lines. The first line contains an
integer N representing the number of anthills in the colony
(2
N105). Each of the next N - 1 lines contains two
integers that describe a tunnel. Line i, for
1iN - 1,
contains Ai and Li , indicating that anthill i was connected
directly to anthill Ai with a tunnel of length Li
(
0Aii - 1 and
1Li109). The next line
contains an integer Q representing the number of queries that follow
(1Q105). Each of the next Q lines describes a query
and contains two distinct integers S and T
(0S, TN - 1),
representing respectively the source and target anthills.
The last test case is followed by a line containing one zero.
Output
For each test case output a single line with Q integers, each of them being the length of a shortest path between the pair of anthills of a query. Write the results for each query in the same order that the queries were given in the input.
Sample Input
6 0 8 1 7 1 9 0 3 4 2 4 2 3 5 2 1 4 0 3 2 0 1 2 1 0 0 1 6 0 1000000000 1 1000000000 2 1000000000 3 1000000000 4 1000000000 1 5 0 0
Sample Output
16 20 11 17 1 1 5000000000
找一個樹狀蟻丘的任兩短最短路徑。
找到兩點的 LCA，利用加減法則去計算兩點路徑。
計算每個點到根的最短路徑，shortest path = dist[x] + dist[y] - 2*dist[LCA(x, y)]
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
//offline LCA problem, solution by Tarjan algorithm
struct edge {
int to, v;
edge(int a=0, int b=0):
to(a), v(b) {}
};
vector<edge> g[100005];
vector<edge> Q[100005];// query pair, v - input index.
int visited[100005], F[100005];
int LCA[100005];//input query answer buffer.
int findF(int x) {
return F[x] == x ? x : (F[x]=findF(F[x]));
}
void Tarjan(int nd) {// rooted-tree.
F[nd] = nd;
for(int i = 0; i < g[nd].size(); i++) {//son node.
Tarjan(g[nd][i].to);
F[findF(g[nd][i].to)] = nd;
}
visited[nd] = 1;
for(int i = 0; i < Q[nd].size(); i++) {
if(visited[Q[nd][i].to]) {
LCA[Q[nd][i].v] = findF(Q[nd][i].to);
}
}
}
int x[100005], y[100005];
long long dist[100005];
int main() {
int n, m, i, j, k;
int to, v;
while(scanf("%d", &n) == 1 && n) {
for(i = 0; i < n; i++) {
g[i].clear(), visited[i] = 0;
Q[i].clear();
}
for(i = 1; i < n; i++) {
scanf("%d %d", &to, &v);
g[to].push_back(edge(i, v));
}
scanf("%d", &m);
for(i = 0; i < m; i++) {
scanf("%d %d", &x[i], &y[i]);
Q[x[i]].push_back(edge(y[i], i));
Q[y[i]].push_back(edge(x[i], i));
}
// build distance from root 0.
dist[0] = 0;
for(i = 0; i < n; i++) {
for(j = 0; j < g[i].size(); j++)
dist[g[i][j].to] = dist[i]+g[i][j].v;
}
// offline LCA
Tarjan(0);
for(i = 0; i < m; i++) {
if(i) putchar(' ');
printf("%lld", dist[x[i]]+dist[y[i]]-dist[LCA[i]]*2);
}
puts("");
}
return 0;
}