lca的简单应用
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;
const int N = 2*1e4+10,M = 2*N;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int degree[N];
int root;
//dist[i]从根节点到i的距离
int deep[N],f[N][20],dist[N];
void Add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void bfs(int root)
{
memset(deep,inf,sizeof deep);
queue<int> Q;
Q.push(root);
deep[0]=0,deep[root]=1;
while(!Q.empty())
{
int t=Q.front();Q.pop();
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
if(deep[j]>deep[t]+1)
{
deep[j]=deep[t]+1;
f[j][0]=t;
for(int k=1;k<=15;k++)
f[j][k]=f[f[j][k-1]][k-1];
dist[j]=dist[t]+w[i];
Q.push(j);
}
}
}
}
int lca(int a,int b)
{
if(deep[a]<=deep[b]) swap(a,b);
for(int k=15;k>=0;k--)
if(deep[f[a][k]]>=deep[b]) a=f[a][k];
if(a==b) return b;
for(int k=15;k>=0;k--)
if(f[a][k]!=f[b][k]) a=f[a][k],b=f[b][k];
return f[a][0];
}
int main()
{
ios :: sync_with_stdio(false);
memset(h, -1, sizeof h);
cin >> n >> m;
for(int i=1;i<n;i++)
{
int a,b,c;cin >> a >> b >> c;
Add(a,b,c);Add(b,a,c);
if(a>=b) swap(a,b);
degree[b]++;
}
for(int i=1;i<=n;i++) if(degree[i]==0) root=i;
bfs(root);
while (m -- )
{
int a,b;cin >> a >> b;
int k=lca(a,b);
int ans=dist[a]+dist[b]-2*dist[k];
cout << ans << endl;
}
return 0;
}