/*
最小公共祖先
題意: 給出一顆無(wú)向有邊權(quán)樹, 詢問若干個(gè)(u,v)對(duì)的距離.
所謂LCA 的Tarjan算法, 實(shí)際上就是在建樹的過程中把query中的lca給計(jì)算出來, 所以稱為`離線算法` . 是的, 本質(zhì)就是這么簡(jiǎn)單, 好多解釋都搞復(fù)雜了.
步驟略, 自己google.
理解這個(gè)算法一定要抓住`遞推`的思想(也有遞歸在里面, 也要抓住).
Tarjan是利用并查集實(shí)現(xiàn)的, 在遞推過程中, 一棵樹的root節(jié)點(diǎn)代表這棵樹(聯(lián)系并查集來想), 這樣做的好處是, 如果問點(diǎn)i與j的lca, 我們只要找i,j都屬于的最小的哪棵子樹就行了, 因?yàn)樵撟訕渚褪俏覀兊拇鸢? 那如何確定是那顆子樹呢? 這一點(diǎn)后面再解釋一下.
下面說Tarjan最巧妙的點(diǎn)了. 因?yàn)槭窃诮涞倪^程中計(jì)算所有query, 也就表示我們此刻是否能計(jì)算某一query對(duì)(u,v)的條件是 : u和v是否都已經(jīng)遍歷過. 所以我們可以在遍歷到點(diǎn)v(假設(shè)經(jīng)歷v的時(shí)間比u晚)的時(shí)候把query給計(jì)算出來. 比如lcm(u,v)就是find(u). 那此刻的find(v)和lcm(u,v)相不相等呢? 答案是不相等, 至少在我的代碼實(shí)現(xiàn)上不相等. 因?yàn)閒ather[x]的更新是在`遞歸回去`的時(shí)候更新的, 而此刻在遍歷v點(diǎn), 還沒遞歸回去呢, father[v]當(dāng)然也就沒更新啦.
其實(shí)上一段就已經(jīng)回答了`如何確定哪棵子樹是我們想要的答案`這一問題了. 就是find(u)所代表的子樹! 注意, 是find(u), 不是find(v)! 因?yàn)閡是在v之前已經(jīng)被遍歷過了, 并且遞歸回去過sub_root過了, 也就是father[u]被更新為sub_root了, 所以find(u)可以代表當(dāng)前的sub_tree, 即`最小包含(u,v)子樹`
下面兩個(gè)解釋, 推薦一下. 羅嗦一句, 看代碼更容易理解, 人腦模擬一遍更容易理解
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子節(jié)點(diǎn)tmp, 再更新其father[tmp], 因?yàn)橐ＷC在遞推tmp所代表的子樹時(shí), father[tmp] = tmp, 而與當(dāng)前子樹無(wú)關(guān). 遞歸回來的時(shí)候再把tmp代表的子樹`并入`到當(dāng)前樹里
}
for(int Size = query[now].size(), i = 0; i < Size; i++) {
int tmp = query[now][i];
if(!visit[tmp]) continue; //若visit[tmp] == true, 即表示tmp節(jié)點(diǎn)已經(jīng)遍歷過, 此時(shí)可計(jì)算相應(yīng)的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;
}