求树上任意两点间距离

输入格式

第一行输入节点数 $n$ 和询问数 $m$.

接下来 $n-1$ 行输入边的起点 $u$ 终点 $v$ 和权值 $w$ （双向边）

接下来 $m$ 行输入所需求距离的两点 $u$ $v$.

输出格式

$m$ 行，为每次询问的答案.

主要思路

tarjan 离线求 LCA，dijkstra 求 root 到每点的距离，最后通过 $dis(u,v)=dis(root,u)+dis(root,v)-2 \cdot dis(root,LCA(u,v))$ 求出两点值.

错误代码 (64pts)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void print(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)print(x/10);
	putchar(x%10+'0');
	return;
}
struct Edge{
	int v,w,next;
}edge[4010];
struct Ask{
	int v,id,next,same,vis;
}ask[10010];
int n,m;
int cnt,cnt1,head[2010],head1[2010];
int vis[2010],ans[5010],dis[2010];
int from[2010],to[2010];
priority_queue<pair<int,int> >q;
void add_edge(int u,int v,int w){
	edge[++cnt]=(Edge){v,w,head[u]};
	head[u]=cnt;
}
void add_ask(int u,int v,int id,int pp){
	cnt1++;
	ask[cnt1]=(Ask){v,id,head1[u],cnt1+pp,0};
	head1[u]=cnt1;
}
int fa[2010];
void init(int p){
	for(int i=1;i<=p;i++){
		fa[i]=i;
	}
}
int find(int x){
	if(fa[x]!=x)fa[x]=find(fa[x]);
	return fa[x];
}
bool check(int x,int y){
	return find(x)==find(y);
}
void merge(int x,int y){
	fa[find(y)]=find(x);
}
void tarjan(int u){
	vis[u]=1;
	for(int i=head[u];i;i=edge[i].next){
		if(!vis[edge[i].v]){
			tarjan(edge[i].v);
			merge(u,edge[i].v);
		}
	}
	for(int i=head1[u];i;i=ask[i].next){
		if(vis[ask[i].v]&&!ask[i].vis){
			ans[ask[i].id]=find(ask[i].v);
			ask[i].vis=1;
			ask[ask[i].same].vis=1;
		}
	}
}
signed main(){
	memset(dis,0x7f,sizeof(dis));
	n=read(),m=read();
	init(n);
	for(int i=1;i<=n-1;i++){
		int u=read(),v=read(),w=read();
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	for(int i=1;i<=m;i++){
		from[i]=read(),to[i]=read();
		add_ask(from[i],to[i],i,1);
		add_ask(to[i],from[i],i,-1);
	}
	tarjan(1);
	dis[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].v,w=edge[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(make_pair(-dis[v],v));
			}
		}
	}
	for(int i=1;i<=m;i++){
		print(dis[from[i]]+dis[to[i]]-2*dis[ans[i]]);
		putchar('\n');
	}
	return 0;
}

感谢！