题解 P2912 【[USACO08OCT]牧场散步Pasture Walking】
顾z
2018-09-26 19:23:51
# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/)
~~你没有发现两个字里的blog都不一样嘛~~ qwq
题目描述-->[p2912 牧场散步](https://www.luogu.org/problemnew/show/P2912)
### 题意概括
给定一个**树**,给你Q个询问,每次询问输入一个二元组$(x,y)$,要求求出$(x,y)$的距离.
明显带权lca.
这里写一下递推式
$$f[u][i]=f[f[u][i-1]][i-1]$$
$$gw[u][i]=gw[f[u][i-1]][i-1]+gw[u][i-1]$$
#### 定义：
> $f[u][i]$代表$u$向上跳$2^i$步到达的节点.
>
> $gw[u][i]$代表$u$向上跳$2^i$步到达的节点的边权和.
为什么$f[u][i]=f[f[u][i-1]][i-1]$？
我们从$u$到达$f[u][i]$需要$2^i$步,而到达$f[u][i-1]$需要$2^{i-1}$步,再从这个位置跳$2^{i-1}$步,的话就到达了$f[u][i]$。
$$2^{i-1}+2^{i-1}=2*2^{i-1}=2^{i}$$
又因为我们处理$f[u][i-1]$一定比处理$f[u][i]$要早,所以这样转移即可.
#### 初始化
```c++
f[u][0]=fa;
gw[u][0]=edge[i].w;//即连向u的边权.
```
然后这样这个题就变成了裸的带权lca问题 qwq.
---------------------代码---------------------
```c++
#include<bits/stdc++.h>
#define R register
#define N 1008
using namespace std;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,head[N],tot,m;
int depth[N],f[N][18],gw[N][18];
struct cod{int u,v,w;}edge[N<<1+8];
inline void add(int x,int y,int z)
{
edge[++tot].u=head[x];
edge[tot].v=y;
edge[tot].w=z;
head[x]=tot;
}
void dfs(int u,int fa,int dis)
{
depth[u]=depth[fa]+1;
f[u][0]=fa;gw[u][0]=dis;
for(R int i=1;(1<<i)<=depth[u];i++)
f[u][i]=f[f[u][i-1]][i-1],
gw[u][i]=gw[f[u][i-1]][i-1]+gw[u][i-1];
for(R int i=head[u];i;i=edge[i].u)
{
if(edge[i].v==fa)continue;
dfs(edge[i].v,u,edge[i].w);
}
}
inline int lca(int x,int y)
{
if(depth[x]>depth[y])swap(x,y);
int ans=0;
for(R int i=17;i>=0;i--)
if(depth[y]-(1<<i)>=depth[x])
ans+=gw[y][i],y=f[y][i];
if(x==y)return ans;
for(R int i=17;i>=0;i--)
{
if(f[x][i]==f[y][i])continue;
ans+=gw[x][i]+gw[y][i];
y=f[y][i],x=f[x][i];
}
return (ans+gw[x][0]+gw[y][0]);
}
int main()
{
in(n),in(m);
for(R int i=1,x,y,z;i<n;i++)
{
in(x),in(y),in(z);
add(x,y,z);add(y,x,z);
}
dfs(1,0,0);
for(R int x,y;m;m--)
{
in(x),in(y);
printf("%d\n",lca(x,y));
}
}
```