标准求法
//O(nlogn)-O(logn)
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=;
int first[maxn],next[maxn*],to[maxn*],dis[maxn*];
int n,m;
void AddEdge(int a,int b,int c)
{
to[++m]=b;
dis[m]=c;
next[m]=first[a];
first[a]=m;
}
int dep[maxn],fa[maxn],cost[maxn],anc[][maxn];
void dfs(int x)
{
dep[x]=dep[fa[x]]+;
for(int i=first[x];i;i=next[i])
{
if(to[i]!=fa[x])
{
fa[to[i]]=x;
cost[to[i]]=cost[x]+dis[i];
dfs(to[i]);
}
}
}
void preprocess()
{
for(int i=;i<=n;i++) anc[][i]=fa[i];
for(int j=;(<<j)<=n;j++)
for(int i=;i<=n;i++)
if(anc[j-][i])
{
int a=anc[j-][i];
anc[j][i]=anc[j-][a];
}
}
int LCA(int p,int q)
{
if(dep[p]<dep[q]) swap(p,q);
int log=;
for(;(<<log)<=dep[p];log++); log--;
for(int i=log;i>=;i--) if(dep[p]-dep[q]>=(<<i)) p=anc[i][p];
if(p==q) return p;
for(int i=log;i>=;i--)
if(anc[i][p]!=anc[i][q])
{
p=anc[i][p];
q=anc[i][q];
}
return fa[p];
}
int main()
{
int a,b,c,Q;
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
AddEdge(a,b,c);
AddEdge(b,a,c);
}
scanf("%d",&Q);
dfs();
preprocess();
while(Q--)
{
scanf("%d%d",&a,&b);
c=LCA(a,b);
printf("%d %d\n",dep[a]+dep[b]-dep[c]*+,cost[a]+cost[b]-cost[c]*);
}
return ;
}
欧拉序列套区间最小值
//O(nlogn)-O(1)
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=;
int n,e=;
int first[maxn],next[maxn*],dis[maxn*],to[maxn*];
void AddEdge(int a,int b,int c)
{
to[e]=b;
dis[e]=c;
next[e]=first[a];
first[a]=e++;
}
int fa[maxn],dep[maxn],d[maxn],p[maxn],A[maxn*],z=;
void dfs(int x)
{
dep[x]=dep[fa[x]]+;
p[x]=z; A[z++]=x;
for(int i=first[x];i;i=next[i])
{
if(fa[x]!=to[i])
{
d[to[i]]=d[x]+dis[i];
fa[to[i]]=x;
dfs(to[i]);
A[z++]=x;
}
}
}
int mv[][maxn*],len[maxn*];
void RMQ_init(int m)
{
for(int i=;i<=m;i++) mv[][i]=A[i];
for(int j=;(<<j)<=m;j++)
for(int i=;i+(<<j)<=m+;i++)
{
mv[j][i]=mv[j-][i];
if(dep[mv[j-][i]]>dep[mv[j-][i+(<<(j-))]]) mv[j][i]=mv[j-][i+(<<(j-))];
}
for(int i=;i<=m;i++)
while(<<(len[i]+)<=i) len[i]++;
}
int LCA(int a,int b)
{
if(a<b) swap(a,b);
int k=len[a-b+];
return dep[mv[k][b]]<dep[mv[k][a-(<<k)+]]?mv[k][b]:mv[k][a-(<<k)+];
}
int main()
{
int a,b,c,Q;
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
AddEdge(a,b,c);
AddEdge(b,a,c);
}
dfs();
RMQ_init(z-);
scanf("%d",&Q);
while(Q--)
{
scanf("%d%d",&a,&b);
c=LCA(p[a],p[b]);
printf("%d %d\n",dep[a]+dep[b]-*dep[c]+,d[a]+d[b]-*d[c]);
}
return ;
}
树链剖分
//O(n)-O(logn)
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=;
struct Edge
{
int b,c;
}es[maxn*];
int n,m=;
int first[maxn],next[maxn*];
void AddEdge(int a,int b,int c)
{
es[m]=(Edge){b,c};
next[m]=first[a];
first[a]=m++;
}
int dep[maxn],siz[maxn],son[maxn],fa[maxn],dis[maxn];
void dfs(int x)
{
siz[x]=; dep[x]=dep[fa[x]]+;
for(int i=first[x];i;i=next[i])
{
Edge& e=es[i];
if(e.b!=fa[x])
{
fa[e.b]=x;
dis[e.b]=dis[x]+e.c;
dfs(e.b);
siz[x]+=siz[e.b];
if(siz[son[x]]<siz[e.b]) son[x]=e.b;
}
}
}
int top[maxn];
void build(int x)
{
if(son[x])
{
top[son[x]]=top[x];
build(son[x]);
}
for(int i=first[x];i;i=next[i])
{
Edge& e=es[i];
if(e.b!=fa[x]&&e.b!=son[x])
{
top[e.b]=e.b;
build(e.b);
}
}
}
int query(int va,int vb)
{
int f1=top[va],f2=top[vb];
while(f1!=f2)
{
if(dep[f1]<dep[f2])
{
swap(f1,f2);
swap(va,vb);
}
va=fa[f1]; f1=top[va];
}
if(dep[va]>dep[vb]) swap(va,vb);
return va;
}
int main()
{
int a,b,c,Q;
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
AddEdge(a,b,c);
AddEdge(b,a,c);
}
dfs();
top[]=;
build();
scanf("%d",&Q);
while(Q--)
{
scanf("%d%d",&a,&b);
c=query(a,b);
printf("%d %d\n",dep[a]+dep[b]-*dep[c]+,dis[a]+dis[b]-*dis[c]);
}
return ;
}
Tarjan算法（离线）
//O(n)-O(1)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int n,m;
int first[maxn],next[maxn*],to[maxn*],d[maxn*];
void AddEdge(int a,int b,int c)
{
to[++m]=b;
d[m]=c;
next[m]=first[a];
first[a]=m;
}
int f2[maxn],n2[maxn*],v[maxn*],id[maxn*];
void AddQuery(int a,int b,int c)
{
v[++m]=b;
id[m]=c;
n2[m]=f2[a];
f2[a]=m;
}
int vis[maxn],dis[maxn],dep[maxn],f[maxn],ans[maxn];
int findset(int x) {return x==f[x]?x:f[x]=findset(f[x]);}
void dfs(int x,int fa)
{
f[x]=x; dep[x]=dep[fa]+;
for(int i=first[x];i;i=next[i])
{
if(to[i]!=fa)
{
dis[to[i]]=dis[x]+d[i];
dfs(to[i],x);
f[to[i]]=f[x];
}
}
vis[x]=;
for(int i=f2[x];i;i=n2[i]) if(vis[v[i]]) ans[id[i]]=findset(v[i]);
}
int A[maxn],B[maxn];
int main()
{
scanf("%d",&n);
int a,b,c,Q;
for(int i=;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
AddEdge(a,b,c);
AddEdge(b,a,c);
}
scanf("%d",&Q);
m=;
for(int i=;i<Q;i++)
{
scanf("%d%d",&A[i],&B[i]);
AddQuery(A[i],B[i],i);
AddQuery(B[i],A[i],i);
}
dfs(,);
for(int i=;i<Q;i++) printf("%d %d\n",dep[A[i]]+dep[B[i]]-dep[ans[i]]*+,dis[A[i]]+dis[B[i]]-dis[ans[i]]*);
return ;
}
LCT
//O(n)-O(logn)
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=;
int n,m;
int first[maxn],next[maxn*],to[maxn*],d[maxn*];
void AddEdge(int a,int b,int c)
{
to[++m]=b;
d[m]=c;
next[m]=first[a];
first[a]=m;
}
int ans1,ans2;
struct LCT
{
int pre[maxn],ch[maxn][],fa[maxn],v[maxn],sumv[maxn],s[maxn];
void init()
{
memset(pre,,sizeof(pre));
memset(ch,,sizeof(ch));
s[]=fa[]=v[]=sumv[]=;
}
void maintain(int x)
{
sumv[x]=v[x]+sumv[ch[x][]]+sumv[ch[x][]];
s[x]=s[ch[x][]]+s[ch[x][]]+;
}
void rotate(int x,int d)
{
int y=pre[x],z=pre[y];
ch[y][d^]=ch[x][d];
pre[ch[x][d]]=y;
ch[z][ch[z][]==y]=x;
pre[x]=z;
ch[x][d]=y;
pre[y]=x;
maintain(y);
}
void splay(int x)
{
int rt=x;
while(pre[rt]) rt=pre[rt];
if(rt!=x)
{
fa[x]=fa[rt];
fa[rt]=;
while(pre[x]) rotate(x,ch[pre[x]][]==x);
}
maintain(x);
}
void access(int x)
{
int y=;
for(;x;x=fa[x])
{
splay(x);
fa[ch[x][]]=x;
pre[ch[x][]]=;
ch[x][]=y;
fa[y]=;
pre[y]=x;
y=x;
maintain(x);
}
}
void query(int x,int y)
{
access(y);
for(y=;x;x=fa[x])
{
splay(x);
if(!fa[x])
{
ans1=s[ch[x][]]+s[y]+;
ans2=sumv[ch[x][]]+sumv[y];
return;
}
fa[ch[x][]]=x;
pre[ch[x][]]=;
ch[x][]=y;
fa[y]=;
pre[y]=x;
y=x;
maintain(x);
}
}
}sol;
int vis[maxn];
queue<int> Q;
void BFS(int x)
{
vis[]=; Q.push();
while(!Q.empty())
{
x=Q.front(); Q.pop();
for(int i=first[x];i;i=next[i])
if(!vis[to[i]])
{
vis[to[i]]=;
sol.fa[to[i]]=x;
sol.v[to[i]]=d[i];
Q.push(to[i]);
sol.maintain(to[i]);
}
}
}
int main()
{
scanf("%d",&n);
int a,b,c,Q;
for(int i=;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
AddEdge(a,b,c);
AddEdge(b,a,c);
}
sol.init();
BFS();
scanf("%d",&Q);
while(Q--)
{
scanf("%d%d",&a,&b);
sol.query(a,b);
printf("%d %d\n",ans1,ans2);
}
return ;
}