文章目录

题目链接：

题意：给一棵树，求节点u到v的最短距离
弄一个dep[]数组，dep[u]表示u节点到根节点的深度，然后找到u和v节点的lca
dis[u]表示到根节点的距离，答案就是dis[u]+dis[v]-dis[lca]*2

在线算法

求出dfs序，然后u的dfs序到v的dfs序中深度最小的那个就是lca，用RMQ来维护
据说这道题数据很水，今天重新写的时候，我RMQ那里写彪了都过了，用另外几道题验过了，应该没毛病吧~

#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
int N,Q,n;//表示节点数,询问次数,dfs序长度 
struct Edge
{
	int t,v,nxt;
};
Edge E[maxn<<1];
int head[maxn];
int tot;
void AddEdge(int aa,int bb,int val)
{
	E[++tot].t=bb;
	E[tot].v=val;
	E[tot].nxt=head[aa];
	head[aa]=tot;
}

int dep[maxn],dis[maxn];//表示到根节点的深度和距离
int sa[maxn<<1],rnk[maxn<<1];//sa[i]表示dfs序是i的是原来哪个节点，rnk[i]表示i节点的dfs序是rnk[i]并且是第一次的序
int Time;//表示dfs序
void dfs(int u,int pre,int deep,int d)//弄出dfs序,以及每个节点到根节点的深度和距离 
{
	dep[u]=deep;
	dis[u]=d;
	sa[++Time]=u;//u节点进去的dfs序
	if(rnk[u]==-1)rnk[u]=Time;
	
	for(int i=head[u]; i!=-1; i=E[i].nxt)
	{
		int t=E[i].t;
		int v=E[i].v;
		if(t==pre)continue;
		dfs(t,u,deep+1,d+v);
		sa[++Time]=u;//u节点出来的dfs序
	}
}

int dp[maxn<<1][20];
void RMQ()
{
	n=N*2-1;
	for(int i=1;i<=n;i++)dp[i][0]=sa[i];
	for(int j=1;(1<<j)<=n;j++)
	{
		for(int i=1;i+(1<<j)-1<=n;i++)
		{
			int u=dp[i][j-1],v=dp[i+(1<<(j-1))][j-1];//数据很水这里写错了都能过
			dp[i][j]=dep[u]<=dep[v]?u:v;
		}
	}
}
int LCA(int u,int v)//找u节点和v节点的lca 
{
	int L=rnk[u],R=rnk[v];
	if(L>R)swap(L,R);//注意这里要保证L<=R
	int k=0;
	while((1<<(k+1))<=R-L+1)k++;
	u=dp[L][k],v=dp[R-(1<<k)+1][k];//注意右端点要+1 
	return dep[u]<=dep[v]?u:v;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		memset(rnk,-1,sizeof rnk);
		memset(head,-1,sizeof head);
		tot=Time=0;
		cin>>N>>Q;
		for(int i=1; i<N; i++)
		{
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			AddEdge(u,v,w);
			AddEdge(v,u,w);
		}
		dfs(1,-1,0,0);
		RMQ();
		while(Q--)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			int p=LCA(u,v);
			cout<<dis[u]+dis[v]-dis[p]*2<<endl;
		}
	}
}