什么是欧拉序，可以去这个大佬的博客（https://www.cnblogs.com/stxy-ferryman/p/7741970.html）巨详细
因为欧拉序中的两点之间，就是两点遍历的过程，所以只要找遍历过程中对应的最小的深度就行了，这里用st表存，first存第一个u出现的地方，用value存欧拉序，同时用depth存对应深度
模板
struct node{
int v,next,dist;
}a[maxn<<];
int n,m,tot,len;
int st[maxn<<][], depth[maxn<<],value[maxn<<],first[maxn<<];
int dist[maxn],head[maxn];
void add(int u,int v,int dist0){
a[tot].next=head[u];
a[tot].dist=dist0;
a[tot].v=v;
head[u]=tot++;
}
void dfs(int u,int fa,int d) {
value[++len]=u;depth[len]=d;first[u]=len;
for (int i=head[u];~i;i=a[i].next){
int v=a[i].v;if(v==fa)continue;
dist[v]=dist[u]+a[i].dist;
dfs(v,u,d+);
value[++len]=u;depth[len]=d;
}
}
inline void init(int n){
for(int i=;i<=n;i++)head[i]=-,depth[i]=;
tot=,len=;
}
inline void makest(){
for(it i=;i<=len;i++)st[i][]=depth[i];
for(it i=;<<i<=len;i++){
for(it j=;j+(<<i)-<=len;j++){
st[j][i]=min(st[j][i-],st[j+(<<(i-))][i-]);
}
}
}
inline int dis(int u,int v){
int l=first[u],r=first[v];
if(l>r){swap(l,r);}
int k=log2(r-l+);
int dep=min(st[l][k],st[r-(<<k)+][k]);
return dist[u]+dist[v]-*dist[value[first[dep]]];
}题意：
以1为根的树，两个点之间的最近距离是多少
思路：
模板LCA
用欧拉序+st表
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define it register int
#define inf 0x3f3f3f3f
#define lowbit(x) (x)&(-x)
#define mem(a,b) memset(a,b,sizeof(a))
#define modd 998244353
const int maxn=4e4+;
struct node{
int v,next,dist;
}a[maxn<<];
int n,m,tot,len;
int st[maxn<<][], depth[maxn<<],value[maxn<<],first[maxn<<];
int dist[maxn],head[maxn];
void add(int u,int v,int dist0){
a[tot].next=head[u];
a[tot].dist=dist0;
a[tot].v=v;
head[u]=tot++;
}
void dfs(int u,int fa,int d) {
value[++len]=u;depth[len]=d;first[u]=len;
for (int i=head[u];~i;i=a[i].next){
int v=a[i].v;if(v==fa)continue;
dist[v]=dist[u]+a[i].dist;
dfs(v,u,d+);
value[++len]=u;depth[len]=d;
}
}
inline void init(int n){
for(int i=;i<=n;i++)head[i]=-,depth[i]=;
tot=,len=;
}
inline void makest(){
for(it i=;i<=len;i++)st[i][]=depth[i];
for(it i=;<<i<=len;i++){
for(it j=;j+(<<i)-<=len;j++){
st[j][i]=min(st[j][i-],st[j+(<<(i-))][i-]);
}
}
}
inline int dis(int u,int v){
int l=first[u],r=first[v];
if(l>r){swap(l,r);}
int k=log2(r-l+);
int dep=min(st[l][k],st[r-(<<k)+][k]);
return dist[u]+dist[v]-*dist[value[first[dep]]];
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
init(n);
for(it i=;i<n-;i++){int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
dfs(,,);
makest();
while(m--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",dis(l,r));
}
}
return ;
}
用倍增
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define it register int
#define inf 0x3f3f3f3f
#define lowbit(x) (x)&(-x)
#define mem(a,b) memset(a,b,sizeof(a))
#define modd 998244353
const int maxn=4e4+;
struct node{
int v,next,dist;
}a[maxn<<];
int n,m,tot;
int fath[maxn][], depth[maxn];
int dist[maxn],head[maxn];
void add(int u,int v,int dist0){
a[tot].next=head[u];
a[tot].dist=dist0;
a[tot].v=v;
head[u]=tot++;
}
void dfs(int u,int fa,int d) {
fath[u][]=fa; depth[u]=d;
for(int i=;i<;i++) fath[u][i]=fath[fath[u][i-]][i-];
for (int i=head[u];~i;i=a[i].next){
int v=a[i].v;if(v==fa)continue;
dist[v]=dist[u]+a[i].dist;
dfs(v,u,d+);
}
}
void init(int n){
for(int i=;i<=n;i++)fath[i][]=,dist[i]=,head[i]=-,depth[i]=;
tot=;
}
inline int lca(int x,int y){
if(depth[x]<depth[y])swap(x,y);
int h=depth[x]-depth[y];
for(it i=;h>;i++){
if(h&){
x=fath[x][i];
}
h>>=;
}
if(x==y)return x;
for(it i=;i>=;i--){
if(fath[x][i]!=fath[y][i]){
x=fath[x][i];
y=fath[y][i];
}
}
return fath[x][];
}
inline int dis(int u,int v){
int d=lca(u,v);
return dist[u]+dist[v]-*dist[d];
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
init(n);
for(it i=;i<n-;i++){int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
dfs(,,);
while(m--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",dis(l,r));
}
}
return ;
}