题目很简单，可以用很多方法写
本人只是想练习一下两种求LCA的方法
基于RMQ思想的LCA
#include<cstdio>
#include<algorithm>
using namespace std;const int maxn=40000+100;struct Edge{
int from,to;int len;int next;
}edge[maxn*2];
int head[maxn],tot;int first[maxn],dfs_c[maxn*2],dep_c[maxn*2],dfs_cc;int dis[maxn];
int n,m;int fa[maxn*2][20];
int kaven[20];inline void AddEdge(int u,int v,int len){
edge[tot].from=u;edge[tot].to=v;edge[tot].len=len;edge[tot].next=head[u];head[u]=tot++;edge[tot].from=v;edge[tot].to=u;edge[tot].len=len;edge[tot].next=head[v];head[v]=tot++;
}inline void dfs(int u,int f,int d,int l){
first[u]=++dfs_cc;dfs_c[dfs_cc]=u;dep_c[dfs_cc]=d;dis[u]=l;for(int i=head[u];i!=-1;i=edge[i].next){
Edge e=edge[i];int v=e.to;if(v==f) continue;dfs(v,u,d+1,l+e.len); dfs_c[++dfs_cc]=u;dep_c[dfs_cc]=d;}
}inline void RMQ(){
for(int i=1;i<=dfs_cc;i++) fa[i][0]=i;for(int i=1;(1<<i)<=dfs_cc;i++){
for(int j=1;j+(1<<i)-1<=dfs_cc;j++){
int l=fa[j][i-1];int r=fa[j+(1<<(i-1))][i-1];if(dep_c[l]<dep_c[r]) fa[j][i]=l;else fa[j][i]=r;}}
}inline int getLca(int u,int v){
u=first[u];v=first[v];if(u>v) swap(u,v);int len=v-u;int i;for(i=0;i<20;i++) if(kaven[i+1]>=len) break;int l=fa[u][i];int r=fa[u+(1<<i)][i];if(dep_c[l]<dep_c[r]) return dfs_c[l];return dfs_c[r];
}inline void init(){
tot=dfs_cc=0;for(int i=1;i<=n;i++) head[i]=-1;
}inline void scan_d(int &res){
res=0;char ch;ch=getchar();while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') res=res*10+(ch-'0'),ch=getchar();
}inline void print_d(int res){
if(res>9) print_d(res/10);putchar(res%10+'0');
}int main(){
for(int i=0;i<20;i++) kaven[i]=1<<i;int T;scan_d(T);while(T--){
scan_d(n);scan_d(m);init();for(int i=1;i<n;i++){
int u,v,len;scan_d(u);scan_d(v);scan_d(len);AddEdge(u,v,len);}dfs(1,-1,1,0);RMQ();for(int i=1;i<=m;i++){
int u,v;scan_d(u);scan_d(v);int lca=getLca(u,v);int len=dis[u]+dis[v]-2*dis[lca];printf("%d\n",len);}}
}
tarjan求LCA
#include<cstdio>
#include<algorithm>
using namespace std;const int maxn=40000+100;struct Edge{
int from,to;int len;int next;
}edge[maxn*2];
int head[maxn],tot;struct Query{
int u,v;int lca;int next;
}query[maxn*2];
int head_q[maxn],toq;int dis[maxn];
int n,m;
int fa[maxn];
bool vis[maxn];inline void AddEdge_q(int u,int v){
query[toq].u=u;query[toq].v=v;query[toq].lca=-1;query[toq].next=head_q[u];head_q[u]=toq++;query[toq].u=v;query[toq].v=u;query[toq].lca=-1;query[toq].next=head_q[v];head_q[v]=toq++;
}inline void AddEdge(int u,int v,int len){
edge[tot].from=u;edge[tot].to=v;edge[tot].len=len;edge[tot].next=head[u];head[u]=tot++;edge[tot].from=v;edge[tot].to=u;edge[tot].len=len;edge[tot].next=head[v];head[v]=tot++;
}inline int Find(int x){
if(x!=fa[x]) fa[x]=Find(fa[x]);return fa[x];
}inline void dfs(int u,int l){
vis[u]=true;dis[u]=l;for(int i=head[u];i!=-1;i=edge[i].next){
Edge e=edge[i];int v=e.to;if(vis[v]) continue;dfs(v,l+e.len); fa[v]=u;}for(int i=head_q[u];i!=-1;i=query[i].next){
Query q=query[i];int v=q.v;if(vis[v]){
query[i].lca=query[i^1].lca=Find(v);}}
}inline void init(){
tot=toq=0;for(int i=1;i<=n;i++) head[i]=head_q[i]=-1,fa[i]=i,vis[i]=false;
}inline void scan_d(int &res){
res=0;char ch;ch=getchar();while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') res=res*10+(ch-'0'),ch=getchar();
}inline void print_d(int res){
if(res>9) print_d(res/10);putchar(res%10+'0');
}int main(){
int T;scan_d(T);while(T--){
scan_d(n);scan_d(m);init();for(int i=1;i<n;i++){
int u,v,len;scan_d(u);scan_d(v);scan_d(len);AddEdge(u,v,len);}for(int i=1;i<=m;i++){
int u,v;scan_d(u);scan_d(v);AddEdge_q(u,v);}dfs(1,0);for(int i=1;i<=m;i++){
int j=2*(i-1); // 或者 j = 2*i-1 int u=query[j].u;int v=query[j].v;int lca=query[j].lca;int len=dis[u]+dis[v]-2*dis[lca];printf("%d\n",len);}}
}