Luogu P3379 最近公共祖先
原题展现
题目描述
如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 (N,M,S),分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 (N-1) 行每行包含两个正整数 (x, y),表示 (x) 结点和 (y) 结点之间有一条直接连接的边(数据保证可以构成树)。
接下来 (M) 行每行包含两个正整数 (a, b),表示询问 (a) 结点和 (b) 结点的最近公共祖先。
输出格式
输出包含 (M) 行,每行包含一个正整数,依次为每一个询问的结果。
样例输入 #1
5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5
样例输出 #1
4 4 1 4 4
提示
对于 (30%) 的数据,(Nleq 10),(Mleq 10)。
对于 (70%) 的数据,(Nleq 10000),(Mleq 10000)。
对于 (100%) 的数据,(Nleq 500000),(Mleq 500000)。
样例说明:
该树结构如下:
第一次询问:(2, 4) 的最近公共祖先,故为 (4)。
第二次询问:(3, 2) 的最近公共祖先,故为 (4)。
第三次询问:(3, 5) 的最近公共祖先,故为 (1)。
第四次询问:(1, 2) 的最近公共祖先,故为 (4)。
第五次询问:(4, 5) 的最近公共祖先,故为 (4)。
故输出依次为 (4, 4, 1, 4, 4)。
解析
本题是 LCA 的模板
LCA 的做法很多,比如暴力跳,倍增
暴力跳
让深度大的一点不断向上跳,直到两点深度相等
如果两点深度相同但是并不相等,可以两点一起跳
在随机数据下表现优异,因为树会比较平衡,所以近似(O(log n))
通常会被卡成单次(O(n)),其实不难构造,可以构造一个深度大的树(比如链)
本人出的一道题思想类似这样,不过这道题保证了平衡
倍增法
考虑一次跳多一点
记(fa_{u,k})表示距离(u)的边数为(2^k)的祖先节点则(fa_{u,k}=fa_{fa_{u,k-1},k-1})可以通过dfs求出(fa)
如果求LCA,我们可以很快让两点来到相同的深度
考虑求两点深度差,将差二进制拆分,每次跳一个(2)的幂,时间复杂度(O(log n))
当然,没必要真的二进制拆分,因为我们要知道是(2)的几次幂,所以用cmath
的log2
更加方便
这里有一个优化:用(O(n))的时间复杂度递推求出log2
的值
然后,如果两点深度相同不相等,有一个自认为巧妙的方法求解
一个性质:如果两点跳到LCA了,继续向上跳依然相等(易证)
如果两点向上跳不相等,那么一定可以继续跳
于是想到一个办法:尝试枚举(i)从(31)到(0),表示尝试跳(2^i)
如果向上跳不相同的话,就向上跳,这样,枚举完,LCA就是(fa_{x,0})
核心代码如下,首先是预处理
void dfs(long long x,long long fa) { f[x][0]=fa; dep[x]=dep[fa]+1; for(int i=1;i<=31;i++) { f[x][i]=f[f[x][i-1]][i-1]; } for(int i=h[x];i;i=a[i].next) { if(a[i].to!=fa) { dfs(a[i].to,x); } } }
然后是求解
if(dep[x]<dep[y]) { swap(x,y); } while(dep[x] > dep[y]) { x = f[x][lg[dep[x]-dep[y]] - 1]; } if(x==y) { cout<<x<<endl; continue; } for(int k = lg[dep[x]] - 1; k >= 0;k--) { if(f[x][k] != f[y][k]) { x = f[x][k], y = f[y][k]; } }
于是,我们得到了一个严格的(O(log n))算法
Luogu P1967 [NOIP2013 提高组] 货车运输
原题展现
题目描述
A 国有 (n) 座城市,编号从 (1) 到 (n),城市之间有 (m) 条双向道路。每一条道路对车辆都有重量限制,简称限重。
现在有 (q) 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。
输入格式
第一行有两个用一个空格隔开的整数 $ n,m$,表示 (A) 国有 $ n$ 座城市和 (m) 条道路。
接下来 (m) 行每行三个整数 (x, y, z),每两个整数之间用一个空格隔开,表示从 $x $ 号城市到 $ y $ 号城市有一条限重为 (z) 的道路。
注意: (x neq y),两座城市之间可能有多条道路 。
接下来一行有一个整数 (q),表示有 (q) 辆货车需要运货。
接下来 (q) 行,每行两个整数 (x,y),之间用一个空格隔开,表示一辆货车需要从 (x) 城市运输货物到 (y) 城市,保证 (x neq y)
输出格式
共有 (q) 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。
如果货车不能到达目的地,输出 (-1)。
样例输入 #1
4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3
样例输出 #1
3 -1 3
提示
对于 (30%) 的数据,(1 le n < 1000),(1 le m < 10,000),(1le q< 1000);
对于 (60%) 的数据,(1 le n < 1000),(1 le m < 5times 10^4),(1 le q< 1000);
对于 (100%) 的数据,(1 le n < 10^4),(1 le m < 5times 10^4),$1 le q< 3times 10^4 $,(0 le z le 10^5)。
解析
因为我们想要经过的最小边最大,那么不妨构造一个最大生成树(建议使用克鲁斯卡尔算 法),这样每条边都能尽可能大
然后问题转换为树上查询,同样利用倍增法求(x->LCA,y->LCA)路径中的最小边,也是可以预处理的
不过问题不保证树联通,需要判断是否有解
克鲁斯卡尔的优势就体现出来了,我们已经处理了并查集,如果两点祖先不同就直接判断为无解
核心代码如下(码风十分奇怪)
Duck006[DuckOI]Kill the Duck
原题展现
温馨提示
Duck非常不要脸,单推自己的题
后来发现其实有好多一样的题
- 贪玩的小孩
- HDU 2586 How far away?
题目描述
XCR是世界名列前茅的OIer,今天在打模拟赛。
他已经AC了前四道题,准备暴切第五题,看着这个题面,突然发现不太对....
他一看五道题的名字
XCR十分生气,想要杀了DengDuck
DengDuck跑到了一个有(n)个结点,(n-1)条边的树上
这个树的每个边都是无向的,都有边权
XCR现在有(m)次询问,第(i(1 leq i leq m))次给出两个正整数(x_i)和(y_i),含义如下
DengDuck 在点 (x_i(1 leq x_i leq n)) 上,XCR在点 (y_i(1 leq y_i leq n)) 上
对于每次询问,请问XCR离DengDuck的距离是多少?
输入格式
第一行一个整数(n)
接下来(n-1)行每行三个正整数分别表示一条边的起点,终点,边权
第(n+1)行一个正整数(m)
接下来(m)行每行两个正整数(x_i)和(y_i)
输出格式
有(m)行,每行一个正整数,表示DengDuck和XCR的距离
样例输入 #1
3 1 2 3 2 3 4 2 1 2 1 3
样例输出 #1
3 7
样例输入 #2
3 1 3 10 1 2 13 5 1 1 2 2 3 1 2 1 1 3
样例输出 #2
0 0 10 13 10
样例输入 #3
14 5 7 12 7 11 15 5 14 12 14 3 17 7 1 19 14 4 14 1 12 16 1 6 16 12 9 19 9 10 10 7 2 11 4 8 10 2 13 14 17 6 11 14 14 13 11 6 10 12 6 8 7 9 9 10 11 13 10 1 4 2 12 13 4 2 7 2 1 12 2 10 11 4 7
样例输出 #3
50 0 40 61 32 48 0 79 89 57 46 63 11 30 46 79 38
提示
对于一定的数据 | (n,m)的范围 | 特殊限制 |
---|---|---|
前(5%)的数据 | (1~20) | 无 |
前(20%)的数据 | (1~3000) | 无 |
另外的(5%)的数据 | (1~3000) | (m=1) |
所有数据 | (1~100000) | 无 |
解析
预处理出(dis_i)表示点(i)到根(1)的距离,答案是(dis_x+dis_y-2dis_{lca(x,y)})
非常容易证明
代码如下