hdu 2586 How far away ?(离线求最近公共祖先)

时间:2021-06-13 16:33:54
 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
#include<map>
using namespace std; const int mx=4e4+;
struct N
{
int v,d;
N(int x,int y)
{
v=x;
d=y;
}
};
vector<N>g[mx],q[mx];
int father[mx];
int dis[mx];
bool vs[mx];
int ans[mx]; void Init(int n)
{
for (int i=;i<=n;i++)
{
father[i]=i;
dis[i]=;
vs[i]=false;
g[i].clear();
q[i].clear();
}
} int Find(int x)
{
int w=x;
while (w!=father[w]) w=father[w];
while (x!=father[x])
{
int fa=father[x];
father[x]=w;
x=fa;
}
return w;
} void un(int x,int y)
{
int rx=Find(x);
int ry=Find(y);
father[y]=x;
} void dfs(int u,int fa,int d)
{
dis[u]=d;
vs[u]=true;
for (int i=;i<g[u].size();i++)
{
N k=g[u][i];
if (vs[k.v]) continue;
dfs(k.v,u,d+k.d);
}
for (int i=;i<q[u].size();i++)
{
N k=q[u][i];
if (!vs[k.v]) continue;
ans[k.d]=dis[u]+dis[k.v]-*dis[Find(k.v)];
}
un(fa,u);
} int main()
{
int n,m;
int t;
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&m);
Init(n);
for (int i=;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u].push_back(N(v,w));
g[v].push_back(N(u,w));
}
for (int i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
q[u].push_back(N(v,i));
q[v].push_back(N(u,i));
}
dfs(,,);
for (int i=;i<=m;i++) printf("%d\n",ans[i]);
}
}