Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13390 Accepted Submission(s): 5018
Problem Description
There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this “How far is it if I want to go from house A to house B”? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path(“simple” means you can’t visit a place twice) between every two houses. Yout task is to answer all these curious people.
Input
First line is a single integer T(T<=10), indicating the number of test cases.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.
Output
For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.
Sample Input
2
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1
Sample Output
10
25
100
100
【题解】
遇到一个节点x。标记已经走过。
然后查询一下有关这个点的询问点y。
看看有没有y，已经被访问过。
如果访问过。则x和y的最近公共祖先为ff(y);->并查集的找爸爸函数；
当然y的根节点不会总是整棵树的根节点；
因为我们在访问x的出度要dfs下一个节点的时候;
在执行完那个dfs之后才把f[y]=x接上去；
值得注意的是。
只要vis[x]=true放在递归的开头就可以了。
那个询问的则放在递归的开头或结尾都可以的。没有影响。
tarjan算法个人觉得有点麻烦。要开数组很多。
但是好像蛮快的。也蛮容易理解。
值得学学；
找到祖先后输出dis[x]+dis[y]-2*dis[LCA];就是距离了。
这个距离是树上的最短距离。还是很有用的。可以扩展下；
网上找到的模拟过程:
假设我们有一组数据 9个节点 8条边 联通情况如下：
1–2，1–3，2–4，2–5，3–6，5–7，5–8，7–9 即下图所示的树
设我们要查找最近公共祖先的点为9–8，4–6，7–5，5–3；
设f[]数组为并查集的父亲节点数组，初始化f[i]=i，vis[]数组为是否访问过的数组，初始为0;
下面开始模拟过程：
取1为根节点，往下搜索发现有两个儿子2和3；
先搜2，发现2有两个儿子4和5，先搜索4，发现4没有子节点，则寻找与其有关系的点；
发现6与4有关系，但是vis[6]=0，即6还没被搜过，所以不操作；
发现没有和4有询问关系的点了，返回此前一次搜索，更新vis[4]=1；
表示4已经被搜完，更新f[4]=2，继续搜5，发现5有两个儿子7和8;
先搜7，发现7有一个子节点9，搜索9，发现没有子节点，寻找与其有关系的点；
发现8和9有关系，但是vis[8]=0,即8没被搜到过，所以不操作；
发现没有和9有询问关系的点了，返回此前一次搜索，更新vis[9]=1；
表示9已经被搜完，更新f[9]=7，发现7没有没被搜过的子节点了，寻找与其有关系的点；
发现5和7有关系，但是vis[5]=0，所以不操作；
发现没有和7有关系的点了，返回此前一次搜索，更新vis[7]=1；
表示7已经被搜完，更新f[7]=5，继续搜8，发现8没有子节点，则寻找与其有关系的点；
发现9与8有关系，此时vis[9]=1，则他们的最近公共祖先为find(9)=5；
(find(9)的顺序为f[9]=7–>f[7]=5–>f[5]=5 return 5;)
发现没有与8有关系的点了，返回此前一次搜索，更新vis[8]=1；
表示8已经被搜完，更新f[8]=5，发现5没有没搜过的子节点了，寻找与其有关系的点；
发现7和5有关系，此时vis[7]=1，所以他们的最近公共祖先为find(7)=5；
(find(7)的顺序为f[7]=5–>f[5]=5 return 5;)
又发现5和3有关系，但是vis[3]=0，所以不操作，此时5的子节点全部搜完了；
返回此前一次搜索，更新vis[5]=1，表示5已经被搜完，更新f[5]=2；
发现2没有未被搜完的子节点，寻找与其有关系的点；
又发现没有和2有关系的点，则此前一次搜索，更新vis[2]=1；
表示2已经被搜完，更新f[2]=1，继续搜3，发现3有一个子节点6；
搜索6，发现6没有子节点，则寻找与6有关系的点，发现4和6有关系；
此时vis[4]=1，所以它们的最近公共祖先为find(4)=1;
(find(4)的顺序为f[4]=2–>f[2]=2–>f[1]=1 return 1;)
发现没有与6有关系的点了，返回此前一次搜索，更新vis[6]=1，表示6已经被搜完了；
更新f[6]=3，发现3没有没被搜过的子节点了，则寻找与3有关系的点；
发现5和3有关系，此时vis[5]=1，则它们的最近公共祖先为find(5)=1；
(find(5)的顺序为f[5]=2–>f[2]=1–>f[1]=1 return 1;)
发现没有和3有关系的点了，返回此前一次搜索，更新vis[3]=1；
更新f[3]=1，发现1没有被搜过的子节点也没有有关系的点，此时可以退出整个dfs了。
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 50000;
const int MAXM = 250;
vector <int> son[MAXN], w[MAXN], q2[MAXN], idx[MAXN];
int n, m, q1[MAXM][3], f[MAXN];
long long dis[MAXN];
bool vis[MAXN];
void input(int &r)
{
char t = getchar();
while (!isdigit(t)) t = getchar();
r = 0;
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
}
int ff(int x)
{
if (f[x] == x)
return x;
f[x] = ff(f[x]);
return f[x];
}
void tarjan(int x, int fa)
{
vis[x] = true;//一定写在开头
int len = q2[x].size();//下面的询问则写在开头结尾都行
for (int i = 0; i <= len - 1; i++)
{
int y = q2[x][i];
if (vis[y])
q1[idx[x][i]][2] = ff(y);
}
len = son[x].size();
for (int i = 0; i <= len - 1; i++)
{
int y = son[x][i];
if (y != fa)
{
dis[y] = dis[x] + w[x][i];
tarjan(y, x);
int aa = ff(x), bb = ff(y);
f[bb] = aa;
}
}
}
int main()
{
// freopen("F:\\rush.txt", "r", stdin);
int T;
input(T);
while (T--)
{
input(n); input(m);
for (int i = 1; i <= n; i++)
son[i].clear(), w[i].clear(), q2[i].clear(), vis[i] = false, f[i] = i, idx[i].clear();
for (int i = 1; i <= n - 1; i++)
{
int x, y, z;
input(x); input(y); input(z);
son[x].push_back(y);
w[x].push_back(z);
son[y].push_back(x);
w[y].push_back(z);
}
for (int i = 1; i <= m; i++)
{
input(q1[i][0]); input(q1[i][1]);
int x = q1[i][0], y = q1[i][1];
q2[x].push_back(y);
idx[x].push_back(i);
q2[y].push_back(x);
idx[y].push_back(i);
}
dis[1] = 0;
tarjan(1, 0);
for (int i = 1; i <= m; i++)
{
int x = q1[i][0], y = q1[i][1], z = q1[i][2];
printf("%I64d\n", dis[x] + dis[y] - 2 * dis[z]);
}
}
return 0;
}