传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2586
题意:给你N个点,M次询问。1~N-1行输入点与点之间的权值,之后M行输入两个点(a,b)之间的最近距离;
思路:设d[maxn]是当前点到根结点的距离,则答案就是 d[a]-d[lca(a,b)]+d[b]-d[lca(a,b)];
接下来介绍LCA(Least Common Ancestors)
即最近公共祖先,是指在有根树中,找出某两个结点u和v最近的公共祖先。
常见解法一般有三种
这里讲解一种在线算法—倍增
所谓倍增,就是按2的倍数来增大,也就是跳 1,2,4,8,16,321,2,4,8,16,32 …… 不过在这我们不是按从小到大跳,而是从大向小跳,即按……32,16,8,4,2,132,16,8,4,2,1来跳,如果大的跳不过去,再把它调小。
首先我们定义fa[u][j]表示结点u的第2^j祖先
那么要怎么求出全部的fa数组呢
不难发现fa[u][0]就是u的父亲结点
这些父亲结点我们可以直接初始化
对于其他结点则有
f[u][j]=f[ fa[u][j-1] ] [j-1]
什么意思呢
u的第2^(j-1)祖先的第2^(j-1)祖先(2^(j-1)+2^(j-1)) 就是u的第2^j祖先
预处理各节点深度+初始化fa数组
void dfs(int x, int fa)
{
h[x] = h[fa] + 1;
f[x][0] = fa;
for(int i = 1; (1 << i) <= h[x]; i++)
f[x][i] = f[f[x][i - 1]][i - 1];
for(int i = head[x]; i; i = edges[i].next)
{
if(edges[i].to != fa)
{
d[edges[i].to] = d[x] + edges[i].w;
dfs(edges[i].to, x);
}
}
}
预处理之后怎么求解LCA(u,v)呢
我么先假定h[u]>h[v]
则两点深度差 d=h[u]-h[v]
现在我们要做的是把u升到与v同样的深度
while(h[x] > h[y])
x = f[x][lg[h[x] - h[y]] - 1];//因为预处理的log函数是log2(i)+1所以要-1
对于任意一个d
我们都能将其分解为
所以直接可以得到向上走的指数
而log函数需要预处理
for(int i = 1; i <= maxn; i++)//log2(i)+1
{
if((1 << lg[i - 1]) == i)
lg[i] = lg[i - 1] + 1;
else
lg[i] = lg[i - 1];
}
到相同高度后就可以开始查询LCA了
for(int i = lg[h[x]] - 1; i >= 0; i--)
{
if(f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
}
大体思路就是
从u和v最远的祖先开始
如果u的第2^i祖先等于 v的第2^i祖先,就不移动
否则u和v同时上移2^i个深度
最后u的父亲一定是u和v的LCA
#include<iostream>
#include<string.h>
#include<cstdio>
using namespace std;
const int maxn = 4e4 + 10;
int n, m;
int tot;
struct node
{
int to;
int next;
int w;
};
node edges[maxn << 1];
int head[maxn];
int lg[maxn];
int h[maxn];
int d[maxn];//当前结点到根结点的深度
int f[maxn][30];//f[i][j] 表示 i 节点的 2^j 级祖先
void add_edges(int u, int v, int w)
{
edges[++tot].to = v;
edges[tot].next = head[u];
edges[tot].w = w;
head[u] = tot;
}
void dfs(int x, int fa)
{
h[x] = h[fa] + 1;
f[x][0] = fa;
for(int i = 1; (1 << i) <= h[x]; i++)
f[x][i] = f[f[x][i - 1]][i - 1];
for(int i = head[x]; i; i = edges[i].next)
{
if(edges[i].to != fa)
{
d[edges[i].to] = d[x] + edges[i].w;
dfs(edges[i].to, x);
}
}
}
int lca(int x, int y)
{
if(h[x] < h[y])
swap(x, y);
while(h[x] > h[y])
x = f[x][lg[h[x] - h[y]] - 1];
if(x == y)
return x;
for(int i = lg[h[x]] - 1; i >= 0; i--)
{
if(f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
}
return f[x][0];
}
int main()
{
int T;
scanf("%d", &T);
for(int i = 1; i <= maxn; i++)//log2(i)+1
{
if((1 << lg[i - 1]) == i)
lg[i] = lg[i - 1] + 1;
else
lg[i] = lg[i - 1];
}
while(T--)
{
tot = 0;
memset(head, 0, sizeof(head));
scanf("%d%d", &n, &m);
int i, j, k;
for(int t = 1; t < n; t++)
{
scanf("%d%d%d", &i, &j, &k);
add_edges(i, j, k);
add_edges(j, i, k);
}
dfs(1, -1);
for(int t = 1; t <= m; t++)
{
scanf("%d%d", &i, &j);
cout << d[i] + d[j] - 2 * d[lca(i, j)] << endl;
}
}
}