用到的各个数组的意义
anc[i][j]表示从点i向根节点走（2^j)步到达的点的编号
dep[i]表示点i的深度
dis[i]表示点i到根节点之间的距离（i到根节点的简单路径上边的权值之和）
算法分析：
（1）题目给出了一颗无根树，因此我们建双向边，并任意选一个点作为根节点（我选择1）
（2）LCA的路径分解性质：
由于点x，y之间的路径(x——>y)可以分解成(x———>LCA(x,y))和
LCA（x,y)———>y两条路径。
因此x，y直接的距离为dis{x}+dis{y}-2*dis{LCA(x,y)}
（3）此时直接考虑求出LCA（x,y)
倍增求LCA：
（1）令dep{x}>dep{y},找到x的一个祖先，该祖先与y深度相等
（2）从该祖先和y出发，每次将两个点都向根节点走一步，直到找到在某一个位置，使得两点同时到达此位置，则此位置为LCA（x，y）
（3）一步一步向根节点走显然太慢，因此考虑用倍增加速该过程
最终复杂度O（nlogn+mlogn）
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
int n,m,anc[maxn][40],dep[maxn],dis[maxn],indu[maxn];
int head[maxn],ecnt=-1;
struct mint
{
int nxt,v,w;
}e[maxn<<1];
void addline(int u,int v,int w)
{
e[++ecnt].nxt=head[u];
e[ecnt].v=v;
e[ecnt].w=w;
head[u]=ecnt;
}
void dfs(int x,int fa,int w)
{
dep[x]=dep[fa]+1;
anc[x][0]=fa;
dis[x]=dis[fa]+w;
for(int i=1;i<=20;++i) anc[x][i]=anc[anc[x][i-1]][i-1];
for(int i=head[x];~i;i=e[i].nxt)
{
if(e[i].v!=fa) dfs(e[i].v,x,e[i].w);
}
return;
}//预处理出dis，anc，dep数组
int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;--i)
{
if(dep[anc[x][i]]>=dep[y]) x=anc[x][i];
}//调整两点深度，是两点深度相等
if(x==y) return x;//若深度相等时两点重合，则y为x的祖先，二者LCA为y（此时x也在y的位置上）
for(int i=20;i>=0;--i)
{
if(anc[x][i]!=anc[y][i])
{
x=anc[x][i];
y=anc[y][i];
}
} //每次向上走相同距离
return anc[x][0];
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=1;i<=n-1;++i)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
addline(a,b,c);
addline(b,a,c);
}
dfs(1,1,0);
int x,y;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
int fa=LCA(x,y);
int ans=dis[x]+dis[y]-2*dis[fa];
printf("%d\n",ans);
}
return 0;
}
tips：
就这水题我debug还用了30min
（1）head记得赋初值
(2）如果在树上建了双向边，那么遍历其子节点时，一定要写成
if（e[i].v!=fa[x]) dfs(e[i].v,x),避免回到x的父节点。
否则会一直递归下去，直到爆栈。特征就是MLE（其实是RE，但是爆栈了所以也是爆空间）
（3)手动输出式的断点找bug是真的好用