Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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 (2N10⁵). Each of the next N - 1 lines contains two integers that describe a tunnel. Line i, for 1iN - 1, contains A_i and L_i , indicating that anthill i was connected directly to anthill A_i with a tunnel of length L_i ( 0A_ii - 1 and 1L_i10⁹). The next line contains an integer Q representing the number of queries that follow (1Q10⁵). 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;
}