题目描述 Description
小机房有棵焕狗种的树，树上有N个节点，节点标号为0到N-1，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节 点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告 诉他们最少需要花费多少精力
输入描述 Input Description
第一行一个n，接下来n-1行每一行有三个整数u，v, c 。表示节点 u 爬到节点 v 需要花费 c 的精力。
第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点
第n+1行有一个整数m表示有m次询问。接下来m行每一行有两个整数 u ，v 表示两只虫子所在的节点
输出描述 Output Description
一共有m行，每一行一个整数，表示对于该次询问所得出的最短距离。
样例输入 Sample Input
3
1 0 1
2 0 1
3
1 0
2 0
1 2
1 0 1
2 0 1
3
1 0
2 0
1 2
样例输出 Sample Output
1
1
2
1
2
数据范围及提示 Data Size & Hint
1<=n<=50000， 1<=m<=75000， 0<=c<=1000
lca找公共祖先。
暴力：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int first[233333], next[233333], tot = 0;
int fa[233333], sd[233333], val[233333];
bool use[233333];
struct qer
{
int from, to, cost;
}es[100005];
inline void init()
{
memset(first, -1, sizeof(first));
tot = 0;
}
inline void build(int f, int t, int d)
{
es[++tot] = (qer){f, t, d};
next[tot] = first[f];
first[f] = tot;
}
inline void dfs(int x)
{
int v;
for(int i = first[x];i != -1;i = next[i])
{
v = es[i].to;
if(!use[v])
{
use[v] = 1;
val[v] = es[i].cost;
sd[v] = sd[x] + 1;
fa[v] = x;
dfs(v);
}
}
}
inline int lca(int a, int b)
{
int ans = 0;
if(sd[a] < sd[b])
swap(a, b);
while(sd[a] > sd[b])
{
ans += val[a];
a = fa[a];
}
while(a != b)
{
ans += val[a];
ans += val[b];
a = fa[a];
b = fa[b];
}
return ans;
}
int main()
{
init();
int n;
scanf("%d", &n);
for(int i = 1;i < n;i ++)
{
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
build(u, v, c);
build(v, u, c);
}
sd[0] = 1;
val[0] = 1;
dfs(0);
int m, ans;
scanf("%d", &m);
for(int i = 1;i <= m;i ++)
{
int u, v;
scanf("%d%d", &u, &v);
ans = lca(u, v);
printf("%d\n", ans);
}
return 0;
}
倍增：
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct bian
{
int from,to,quan;
}b[100005];
int tot=1;
int t[50005][21];
int c[50005][21];
int nxt[100005];
int fa[50005];
int first[50005];
int dis[50005];
void build(int f,int t,int c)
{
b[++tot].from=f;
b[tot].to=t;
b[tot].quan=c;
nxt[tot]=first[f];
first[f]=tot;
}
int sd[50005];
void dfs(int dq,int s)
{
sd[dq]=s;
int x;
for(int i=first[dq];i;i=nxt[i])
{
x=b[i].to;
if(!sd[x]&&x!=0)
{
fa[x]=dq;
dis[x]=dis[dq]+b[i].quan;
dfs(x,s+1);
}
}
}
int lca(int u,int v)
{
int tt=sd[u]-sd[v],ans;
for(int i=0;i<=20;i++)
{
if((1<<i)&tt)
u=t[u][i];
}
for(int i=20;i>=0;i--)
{
if(t[u][i]!=t[v][i])
{
v=t[v][i];
u=t[u][i];
}
}
if(u!=v)
return fa[u];
return u;
}
int main()
{
int n;scanf("%d",&n);
int u,v,c;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&c);
build(u,v,c);
build(v,u,c);
}
dfs(0,0);
for(int i=0;i<n;i++)
t[i][0]=fa[i];
for(int j=1;j<=20;j++)
for(int i=0;i<n;i++)
t[i][j]=t[t[i][j-1]][j-1];
dis[0]=0;
int m;scanf("%d",&m);
int ans;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
if(sd[u]<sd[v])
swap(v,u);
ans=lca(u,v);
if(ans==u)
printf("%d\n",dis[v]-dis[u]);
else
printf("%d\n",dis[u]+dis[v]-2*dis[ans]);
}
return 0;
}