描述 Description
N 头牛（2<=n<=1000）别人被标记为 1 到 n，在同样被标记 1 到 n 的 n 块土地上吃草，第 i 头牛在第 i 块牧场吃草。 这 n 块土地被 n-1 条边连接。 奶牛可以在边上行走，第 i 条边连接第 Ai，Bi 块牧场，第 i 条边的长度是 Li（1<=Li<=10000）。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。 这些奶牛是非常喜欢交际的，经常会去互相访问, 他们想让你去帮助他们计算 Q(1<=q<=1000) 对奶牛之间的距离。
输入格式 InputFormat
第一行：两个被空格隔开的整数：N 和 Q.
第二行到第 n 行：第 i+1 行有两个被空格隔开的整数：AI，BI，LI.
第 n+1 行到 n+Q 行：每一行有两个空格隔开的整数：P1，P2，表示两头奶牛的编号。
输出格式 OutputFormat
第 1 行到第 Q 行：每行输出一个数，表示那两头奶牛之间的距离。
样例输入 SampleInput
8 4
6 4 5
1 4 3
7 5 5
5 2 3
3 6 4
2 6 2
8 6 8
1 6
8 5
6 4
6 2
样例输出 SampleOutput
8
13
5
2
来源 Source
资格赛
代码 Code
dfs 计算距离，则点 x,y 之间的距离 = dis[x] + dis[y] - 2*dis[lca(x,y)]。LCA 的 Tarjan 离线算法求答案。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct path
{
int to,next,val;
}a[2005];
struct ques
{
int id,to,next;
}c[2005];
int head[2005],qhead[2005];
bool vis[1005];
int dis[1005];
int ans[1005];
int fa[1005];
int i,j,t,n,m,l,r,k,p,q,u,v,w,z,y,x;
inline void ins(int u,int v,int w)
{
a[++m].to=v;a[m].next=head[u];a[m].val=w;
head[u]=m;
}
inline void insq(int u,int v,int w)
{
c[++p].id=w;c[p].to=v;c[p].next=qhead[u];
qhead[u]=p;
}
void dfs(int s)
{
int i,j,t;
vis[s]=true;
for (i=head[s];i;i=a[i].next) if (vis[a[i].to]==false)
{
dis[a[i].to]=dis[s]+a[i].val;
dfs(a[i].to);
}
}
inline int getfa(int s)
{
if (fa[s]==s) return s;
else fa[s]=getfa(fa[s]);
return fa[s];
}
void lca(int s)
{
int i,j,t;
vis[s]=true;
fa[s]=s;
for (i=qhead[s];i;i=c[i].next) if (vis[c[i].to]==true)
{
ans[c[i].id]=dis[s]+dis[c[i].to]-2*dis[getfa(c[i].to)];
}
for (i=head[s];i;i=a[i].next) if (vis[a[i].to]==false)
{
lca(a[i].to);
fa[a[i].to]=s;
}
}
int main()
{
memset(vis,false,sizeof(vis));
scanf("%d%d",&n,&q);
m=0;
for (i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
ins(u,v,w);ins(v,u,w);
}
p=0;
for (i=1;i<=q;i++)
{
scanf("%d%d",&u,&v);
insq(u,v,i);insq(v,u,i);
}
dfs(1);
memset(vis,false,sizeof(vis));
lca(1);
for (i=1;i<=q;i++) printf("%dn",ans[i]);
return 0;
}