链接：https://vjudge.net/problem/HDU-2586
题意：
勇气小镇是一个有着n个房屋的小镇，为什么把它叫做勇气小镇呢，这个故事就要从勇气小镇成立的那天说起了，
修建小镇的时候，为了让小镇有特色，镇长特地只修了n-1条路，并且规定说，所有在勇气小镇的村民，每一次出门必须规划好路线,
路线必须满足在到达终点之前绝对不走回头路。每个人都要这样，不然那个人就不配在小镇生活下去，因为他没有这个勇气。
事实上，这并不能算一项挑战，因为n-1条路已经连通了每户人家，不回头地从起点到终点，只是一个时间上的问题。
由于小镇上的福利特别好，所以小懒入住了这个小镇，他规划了m次的行程，每次从L房屋到R房屋,他想问你他每次从L房屋到R房屋需要走多远的路。
思路：
Tarjan离线算法， 第i个查询的最短路为dis[s[i]]+dis[e[i]]-2*dis[fas[i]]
代码：
#include <iostream>
#include <memory.h>
#include <string>
#include <istream>
#include <sstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <queue>
#include <math.h>
#include <cstdio>
#include <set>
#include <iterator>
#include <cstring>
using namespace std; typedef long long LL;
const int MAXN = 4e4+10;
struct Node
{
int from_, to_, dist_;
Node(int from, int to, int dist):from_(from), to_(to), dist_(dist){}
};
vector<Node> G[MAXN];
int fa[MAXN], dis[MAXN];
int vis[MAXN], fas[MAXN];
int s[MAXN], e[MAXN];
int n, m, l, r, v;
int root, res; int Get_F(int x)
{
if (fa[x] == x)
return x;
fa[x] = Get_F(fa[x]);
return fa[x];
} void Merge(int u, int v)
{
int tv = Get_F(v);
int tu = Get_F(u);
if (tv != tu)
fa[v] = u;
} void Tarjan(int u)
{
vis[u] = 1;
for (int i = 1;i <= m;i++)
{
if (s[i] == u && vis[e[i]] == 1)
fas[i] = Get_F(e[i]);
if (e[i] == u && vis[s[i]] == 1)
fas[i] = Get_F(s[i]);
}
for (int i = 0;i < G[u].size();i++)
{
Node node = G[u][i];
if (!vis[node.to_])
{
dis[node.to_] = dis[node.from_] + node.dist_;
Tarjan(node.to_);
Merge(node.from_, node.to_);
}
}
} void init()
{
for (int i = 1;i <= n;i++)
{
G[i].clear();
fa[i] = i;
}
memset(vis, 0, sizeof(vis));
memset(dis, 0, sizeof(vis));
} int main()
{
ios::sync_with_stdio(false);
cin.tie(0); int t;
cin >> t;
while (t--)
{
cin >> n >> m;
init();
for (int i = 1;i < n;i++)
{
cin >> l >> r >> v;
G[l].emplace_back(l, r, v);
G[r].emplace_back(r, l, v);
}
for (int i = 1;i <= m;i++)
{
cin >> l >> r;
s[i] = l;
e[i] = r;
}
dis[1] = 0;
Tarjan(1);
for (int i = 1;i <= m;i++)
{
cout << dis[s[i]]+dis[e[i]]-2*dis[fas[i]] << endl;
}
} return 0;
}