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/%/) 的数据，/(N/leq 10/)，/(M/leq 10/)。

对于 /(70/%/) 的数据，/(N/leq 10000/)，/(M/leq 10000/)。

对于 /(100/%/) 的数据，/(N/leq 500000/)，/(M/leq 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/)，/(1/le q< 1000/)；

对于 /(60/%/) 的数据，/(1 /le n < 1000/)，/(1 /le m < 5/times 10^4/)，/(1 /le q< 1000/)；

对于 /(100/%/) 的数据，/(1 /le n < 10^4/)，/(1 /le m < 5/times 10^4/)，$1 /le q< 3/times 10^4 $，/(0 /le z /le 10^5/)。

解析

因为我们想要经过的最小边最大，那么不妨构造一个最大生成树（建议使用克鲁斯卡尔算 法），这样每条边都能尽可能大

然后问题转换为树上查询，同样利用倍增法求/(x->LCA,y->LCA/)路径中的最小边，也是可以预处理的

不过问题不保证树联通，需要判断是否有解

克鲁斯卡尔的优势就体现出来了，我们已经处理了并查集，如果两点祖先不同就直接判断为无解

核心代码如下（码风十分奇怪）

#include<bits/stdc++.h> #define ll long long using namespace std; struct road {     ll s,t,w; }r[200005]; struct node {     ll to,next,w; }a[200005]; ll n,m,t,k,x,y,fa2[100005],h[100005],fa[100005][33],f[100005][33],dep[100005],lg[100005]; bool cmp(road x,road y) {     return x.w>y.w; } void add(int x,int y,int z) {     t++;     a[t].to=y;     a[t].w=z;     a[t].next=h[x];     h[x]=t; } int find(int x) {     if(fa2[x]==x)return x;     return fa2[x]=find(fa2[x]); } void dfs(long long x,long long fn) {     fa[x][0]=fn;     dep[x]=dep[fn]+1;      for(int i=1;i<=31;i++)     {         fa[x][i]=fa[fa[x][i-1]][i-1];         f[x][i]=min(f[x][i-1],f[fa[x][i-1]][i-1]);//f数组表示x到fa[x][i]路径的最小值     }     for(int i=h[x];i;i=a[i].next)     {         if(a[i].to!=fn)         {                f[a[i].to][0]=a[i].w;             dfs(a[i].to,x);         }     } } int lca(int x,int y) {     if(dep[x]<dep[y])     {         swap(x,y);     }        while(dep[x] > dep[y])     {         x = fa[x][lg[dep[x]-dep[y]] - 1];     }     if(x==y)     {         return x;     }     for(int k = lg[dep[x]] - 1; k >= 0;k--)      {         if(fa[x][k] != fa[y][k])          {             x = fa[x][k], y = fa[y][k];         }     }         return fa[x][0]; } int work(int x,int y)//求解x到y路径的最小值，保证y是x祖先 {     ll ans=1e9,deph=dep[x]-dep[y];     while(deph!=0)     {         ll t=lg[deph]-1;         ans=min(ans,f[x][t]);         x=fa[x][t];         deph=dep[x]-dep[y];     }     return ans; } int main() {      cin>>n>>m;     for(int i=1;i<=n;i++)     {         fa2[i]=i;         lg[i] = lg[i-1] + (1 << lg[i-1] == i);     }     for(int i=1;i<=m;i++)     {         cin>>r[i].s>>r[i].t>>r[i].w;     }     sort(r+1,r+m+1,cmp);//克鲁斯卡尔     int k=n-1;     for(int i=1;i<=m;i++)     {         if(k==0)break;         if(find(r[i].s)!=find(r[i].t))         {             add(r[i].s,r[i].t,r[i].w);             add(r[i].t,r[i].s,r[i].w);             fa2[find(r[i].s)]=find(r[i].t);             k--;         }     }     for(int i=1;i<=n;i++)     {         if(find(i)==i)         {             dfs(i,0);         }     }     cin>>k;     for(int i=1;i<=k;i++)     {         cin>>x>>y;         if(find(x)!=find(y))         {             cout<<-1<<endl;             continue;         }         int lcah=lca(x,y);         cout<<min(work(x,lcah),work(y,lcah))<<endl;     } } 

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 

提示

解析

预处理出/(dis_i/)表示点/(i/)到根/(1/)的距离，答案是/(dis_x+dis_y-2dis_{lca(x,y)}/)

非常容易证明

代码如下

#include <bits/stdc++.h> using namespace std; int n, k, b[1000005], x, y, z, tot, h[500005], len[500005], fa[500005][33], dep[500005], lg[500005],     f[1000005], ans; struct node {     int to, next, w; } a[1000005]; void dfs(long long x, long long fn, long long l) {     fa[x][0] = fn;     dep[x] = dep[fn] + 1;     len[x] = l;     for (int i = 1; i <= 31; i++) {         fa[x][i] = fa[fa[x][i - 1]][i - 1];     }     for (int i = h[x]; i; i = a[i].next) {         if (a[i].to != fn) {             dfs(a[i].to, x, l + a[i].w);         }     } } int lca(int x, int y) {     if (dep[x] < dep[y]) {         swap(x, y);     }     while (dep[x] > dep[y]) {         x = fa[x][lg[dep[x] - dep[y]] - 1];     }     if (x == y) {         return x;     }     for (int k = lg[dep[x]] - 1; k >= 0; k--) {         if (fa[x][k] != fa[y][k]) {             x = fa[x][k], y = fa[y][k];         }     }     return fa[x][0]; } void add(int x, int y, int z) {     ++tot;     a[tot].to = y;     a[tot].next = h[x];     a[tot].w = z;     h[x] = tot; } void answer(int x, int fn) {     for (int i = h[x]; i; i = a[i].next) {         if (a[i].to != fn) {             answer(a[i].to, x);             f[x] += f[a[i].to];         }     }     ans = max(ans, f[x]); } int main() {     cin >> n;     for (int i = 1; i <= n; ++i) {         lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);     }     for (int i = 1; i <= n - 1; i++) {         cin >> x >> y >> z;         add(x, y, z);         add(y, x, z);     }     dfs(1, 0, 0);     cin >> k;     for (int i = 1; i <= k; i++) {         cin >> x >> y;         int t = lca(x, y);         cout << len[x] + len[y] - 2 * len[t] << endl;     } }