tarjan算法，都是用什么low数组什么的，我看的这个题解是并查集做的。用并查集建树。很强。
一定一定要善于总结，善于反思
预处理：
1.链式前向星存图
2.设置vis数组。tarjan算法是深搜，而且存的是双向边，不设置vis的话可能掉过头来又会访问之，就嗝屁了。对每个点设置vis数组
3.有很多次询问，对于每次询问都要给出答案。所以对于每个点的询问，都要给出下面的代码：
for(int i=0;i<query[u].size();i++)
{
int t=query[u][i];//query[u][i]是询问的点，i只是按下标存的点
if(!vis[t]) continue; //没被访问过，说明深搜没有到。这个询问的点距离不算
ans[num[u][i]] = dis[u]+dis[t]-2*dis[find(t)];
}
其中，num[u][i]存放的是询问的询问的顺序是第几个，query[u][i]是存放的询问的点，u~v的点的最短距离。
4.dis[i]是 i 到1的距离。u~v的距离=dis[u]+dis[v]-2*dis[u,v的最近公共祖先]
5.将1点设置为根节点，tarjan的时候从1开始，val是1到该点的距离。
6.（坑）并查集里的并操作，必须是f[to]=from。因为是有向边不是无向边，to的father必须是from。DSB
tarjan算法步骤：tarjan(u,val):
1.设置vis[u]=1,dis[u]=val;
2.访问所有u开头的边，如果访问过continue，没访问过，val+e[i].w，深搜之。
3.深搜完了说明当前搜到的都是一根绳上的蚂蚱，都Union起来
4.看看有没有当前节点的查询，有的话就算一下。
void tarjan(int u,int val) //u是点，val是源点到u的路径和。 初始点是1，1到1的距离是0，后面就要加上边的权值
{
vis[u]=1; dis[u]=val;
for(int i=head[u];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(vis[to]) continue; //双向边，防止重复
tarjan(to,val+e[i].w); //dfs
Union(u,to); //合并
}
for(int i=0;i<query[u].size();i++)
{
int t=query[u][i];//query[u][i]是询问的点，i只是按下标存的点
if(!vis[t]) continue; //没被访问过，说明深搜没有到。这个询问的点距离不算
ans[num[u][i]] = dis[u]+dis[t]-2*dis[find(t)];
}
}
ＡＣ：
#include<iostream>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
using namespace std;
//const int N = 8*1e7+1;
const int maxn= 40010*2;
int head[maxn],vis[maxn];
int f[maxn],dis[maxn];
int ans[maxn];
vector<int> query[maxn];
vector<int> num[maxn];
int n,m;
int cnt;
struct edge{
int to,w,next;
}e[maxn*2]; //存的是双向边
void Init()
{
cnt=0;
memset(ans,0,sizeof(ans));
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis)); //设置为0 不同于dijkstra
for(int i=1;i<maxn;i++) f[i]=i;
query->clear();
num->clear();
}
int find(int x)
{
if(x==f[x]) return x;return f[x] =find(f[x]);
}
void Union(int a,int b) //a=u b=to
{
a=find(a);b=find(b);f[b]=a;//f[a]=b就不对。因为是从a点到b点，所以a是b的父节点。很细节。
}
void add(int u,int v,int w)
{
e[++cnt].w=w;
e[cnt].to=v;
e[cnt].next=head[u];
head[u] = cnt;
}
void tarjan(int u,int val) //u是点，val是源点到u的路径和。 初始点是1，1到1的距离是0，后面就要加上边的权值
{
vis[u]=1; dis[u]=val;
for(int i=head[u];i!=-1;i=e[i].next)
{
int to=e[i].to;
if(vis[to]) continue; //双向边，防止重复
tarjan(to,val+e[i].w); //dfs
Union(u,to); //合并
}
for(int i=0;i<query[u].size();i++)
{
int t=query[u][i];//query[u][i]是询问的点，i只是按下标存的点
if(!vis[t]) continue; //没被访问过，说明深搜没有到。这个询问的点距离不算
ans[num[u][i]] = dis[u]+dis[t]-2*dis[find(t)];
}
}
int main()
{
int cishu;
cin>>cishu;
while(cishu--)
{
Init();
cin>>n>>m;
for(int i=1;i<n;i++)
{
int u,v,w; scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w); //双向边
}
for(int i=1;i<=m;i++)
{
int u,v;scanf("%d%d",&u,&v);
query[u].push_back(v);query[v].push_back(u);//query[u]里存的是询问u~v的全部询问的点
num[u].push_back(i);num[v].push_back(i); //num[u]里存的是询问点u是第几次询问
}
tarjan(1,0); //将1设置为根节点，点是1~n的
for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
// cout<<endl;for(int i=1;i<=n;i++)cout<<f[i]<<" ";cout<<endl;
}
}