中国建设工程招标官方网站,专业的门户网站建设方案,wordpress中文模版,网站开发课设P3379
P3379 【模板】最近公共祖先#xff08;LCA#xff09; # 【模板】最近公共祖先#xff08;LCA#xff09;
## 题目描述
如题#xff0c;给定一棵有根多叉树#xff0c;请求出指定两个点直接最近的公共祖先。
## 输入格式
第一行包含三个正整数 $N,M,S$#… P3379
P3379 【模板】最近公共祖先LCA # 【模板】最近公共祖先LCA
## 题目描述
如题给定一棵有根多叉树请求出指定两个点直接最近的公共祖先。
## 输入格式
第一行包含三个正整数 $N,M,S$分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 $N-1$ 行每行包含两个正整数 $x, y$表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边数据保证可以构成树。
接下来 $M$ 行每行包含两个正整数 $a, b$表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。
## 输出格式
输出包含 $M$ 行每行包含一个正整数依次为每一个询问的结果。
## 样例 #1
### 样例输入 #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\%$ 的数据$1 \leq N,M\leq 500000$$1 \leq x, y,a ,b \leq N$**不保证** $a \neq b$。 样例说明
该树结构如下 
第一次询问$2, 4$ 的最近公共祖先故为 $4$。
第二次询问$3, 2$ 的最近公共祖先故为 $4$。
第三次询问$3, 5$ 的最近公共祖先故为 $1$。
第四次询问$1, 2$ 的最近公共祖先故为 $4$。
第五次询问$4, 5$ 的最近公共祖先故为 $4$。
故输出依次为 $4, 4, 1, 4, 4$。 2021/10/4 数据更新 fstqwq应要求加了两组数据卡掉了暴力跳。 #includebits/stdc.h
using namespace std;
const int N1e510,L19;
int n,m,s,f[N][20],head[N],k,dep[N],lo[N];
struct ed{int to,next;
}e[2*N];
void add(int x,int y){e[k].toy;e[k].nexthead[x];head[x]k;
}
void dfs(int x,int fa){f[x][0]fa;dep[x]dep[fa]1;for(int i1;i19;i)f[x][i]f[f[x][i-1]][i-1];for(int ihead[x];i!0;ie[i].next){int toe[i].to;if(to!fa)dfs(e[i].to,x);}
}
int lca(int x,int y){if(dep[x]dep[y])swap(x,y);while(dep[x]dep[y]){xf[x][lo[dep[x]-dep[y]]];//printf(oO%d,%d,%d\n,f[x][lo[dep[x]-dep[y]]],x,y);}if(xy) return x;for(int i19;i0;i--){if(f[x][i]!f[y][i]){xf[x][i];yf[y][i];}}return f[y][0];
}
int main(){//printf(%d,log(1));//memset(head,-1,sizeof(head));scanf(%d%d%d,n,m,s);for(int i2;iN;i){lo[i]lo[i/2]1;}for(int i1;in;i){int x,y;scanf(%d%d,x,y);add(x,y);add(y,x);}dfs(s,0);//for(int i1;in;i)printf(%d ,dep[i]);while(m--){int x,y;scanf(%d%d,x,y);printf(%d\n,lca(x,y));}
}
/*
5 5 4
3 1
2 4
5 1
1 4
2 4
4 2
3 4
4 2
4 5
*/#includebits/stdc.h
using namespace std;
const int N5e510,L19;
int n,m,s,fa[N],head[N],k,dep[N],lo[N],ans[N];
bool vis[N];
vectorint e[N];
vectorpairint,int q[N];
int find(int x){if(fa[x]x)return x;return fa[x]find(fa[x]);
}
void dfs(int x){fa[x]x;vis[x]1;for(int i0;ie[x].size();i){int toe[x][i];if(!vis[to]){dfs(to);fa[to]x;}}for(int i0;iq[x].size();i){int cq[x][i].first,ccq[x][i].second;if(vis[c]){ans[cc]find(c);}}
}
int main(){//printf(%d,log(1));//memset(head,-1,sizeof(head));scanf(%d%d%d,n,m,s);for(int i1;in;i){int x,y;scanf(%d%d,x,y);e[x].push_back(y);e[y].push_back(x);}//for(int i1;in;i)printf(%d ,dep[i]);for(int i1;im;i){int x,y;scanf(%d%d,x,y);q[x].push_back((pairint,int){y,i});q[y].push_back((pairint,int){x,i});}vis[0]1;dfs(s);for(int i1;im;i){printf(%d\n,ans[i]);}
}
/*
5 5 4
3 1
2 4
5 1
1 4
2 4
4 2
3 3
2 2
4 5
*/
