/*
最小公共祖先
題意: 給出一顆無向有邊權樹, 詢問若干個(u,v)對的距離.
所謂LCA 的Tarjan算法, 實際上就是在建樹的過程中把query中的lca給計算出來, 所以稱為`離線算法` . 是的, 本質就是這么簡單, 好多解釋都搞復雜了.
步驟略, 自己google.
理解這個算法一定要抓住`遞推`的思想(也有遞歸在里面, 也要抓住).
Tarjan是利用并查集實現的, 在遞推過程中, 一棵樹的root節點代表這棵樹(聯系并查集來想), 這樣做的好處是, 如果問點i與j的lca, 我們只要找i,j都屬于的最小的哪棵子樹就行了, 因為該子樹就是我們的答案. 那如何確定是那顆子樹呢? 這一點后面再解釋一下.
下面說Tarjan最巧妙的點了. 因為是在建樹的過程中計算所有query, 也就表示我們此刻是否能計算某一query對(u,v)的條件是 : u和v是否都已經遍歷過. 所以我們可以在遍歷到點v(假設經歷v的時間比u晚)的時候把query給計算出來. 比如lcm(u,v)就是find(u). 那此刻的find(v)和lcm(u,v)相不相等呢? 答案是不相等, 至少在我的代碼實現上不相等. 因為father[x]的更新是在`遞歸回去`的時候更新的, 而此刻在遍歷v點, 還沒遞歸回去呢, father[v]當然也就沒更新啦.
其實上一段就已經回答了`如何確定哪棵子樹是我們想要的答案`這一問題了. 就是find(u)所代表的子樹! 注意, 是find(u), 不是find(v)! 因為u是在v之前已經被遍歷過了, 并且遞歸回去過sub_root過了, 也就是father[u]被更新為sub_root了, 所以find(u)可以代表當前的sub_tree, 即`最小包含(u,v)子樹`
下面兩個解釋, 推薦一下. 羅嗦一句, 看代碼更容易理解, 人腦模擬一遍更容易理解
http://www.nocow.cn/index.php/Tarjan%E7%AE%97%E6%B3%95
http://blog.chinaunix.net/uid-1721137-id-181005.html
*/
#include <vector>
#include <stdio.h>
using namespace std;
#define MAXN 40001
#define debug printf("!\n")
vector<int> v[MAXN], w[MAXN], query[MAXN], ans_num[MAXN];
int father[MAXN], dis[MAXN], ans[201];
bool visit[MAXN];
int n;
void init()
{
for(int i = 1; i <= n; i++) {
v[i].clear();
w[i].clear();
ans_num[i].clear();
query[i].clear();
father[i] = i;
dis[i] = 0;
visit[i] = false;
}
}
int find(int x)
{
return x == father[x] ? x : father[x] = find(father[x]);
}
void Union(int x, int y) { father[find(y)] = find(x); }
void Tarjan(int now, int value)
{
visit[now] = true;
dis[now] = value;
for(int Size = v[now].size(), i = 0; i < Size; i++) {
int tmp = v[now][i];
if(visit[tmp] != 0) continue;
Tarjan(tmp, value + w[now][i]);
Union(now, tmp); //注意順序, 先Tarjan子節點tmp, 再更新其father[tmp], 因為要保證在遞推tmp所代表的子樹時, father[tmp] = tmp, 而與當前子樹無關. 遞歸回來的時候再把tmp代表的子樹`并入`到當前樹里
}
for(int Size = query[now].size(), i = 0; i < Size; i++) {
int tmp = query[now][i];
if(!visit[tmp]) continue; //若visit[tmp] == true, 即表示tmp節點已經遍歷過, 此時可計算相應的query
ans[ans_num[now][i]] = dis[now] + dis[tmp] - 2 * dis[find(tmp)];
}
}
int main()
{
int cases, Query, x, y, z;
scanf("%d", &cases);
while(cases--) {
scanf("%d%d", &n, &Query);
init();
for(int i = 1; i < n; i++) {
scanf("%d%d%d", &x, &y, &z);
v[x].push_back(y);
w[x].push_back(z);
v[y].push_back(x);
w[y].push_back(z);
}
for(int i = 0; i < Query; i++) {
scanf("%d%d", &x, &y);
query[x].push_back(y);
query[y].push_back(x);
ans_num[x].push_back(i);
ans_num[y].push_back(i);
}
Tarjan(1, 0);
for(int i = 0; i < Query; i++) printf("%d\n", ans[i]);
}
return 0;
}