设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › C\C++交流 › 【C++板块提升计划】梦想护卫舰 第25关 最近公共祖先
返回列表 发新帖
查看: 2967|回复: 16

[已解决]【C++板块提升计划】梦想护卫舰 第25关 最近公共祖先

[复制链接]
zhangjinxuan
发表于 2023-2-19 10:01:26 | 显示全部楼层 |阅读模式
本帖最后由 zhangjinxuan 于 2023-2-19 15:21 编辑


上一关：性能测试


梦想护卫舰 第25关 最近公共祖先


梦想护卫舰终于继续出发

这时，高山发现，船上有很多人都有亲戚关系，现在给定 N - 1 对人的关系，请求出任意两个人的最年轻的公共祖先是谁

输入格式
第一行包含三个正整数 N,M,S，分别表示人的个数、询问的个数和最老祖先的序号。

接下来 N-1 行每行包含两个正整数 ,x,y，表示第 x 人和第 y 人存在亲戚关系（我们保证能够造成一棵树）。
接下来 M 行每行包含两个正整数 a,b，表示询问第 a 人和第 b 人的最年轻的公共祖先。

输出格式
输出包含 M 行，每行包含一个正整数，依次为每一个询问的结果。

输入样例
  1. 5 5 4
  2. 3 1
  3. 2 4
  4. 5 1
  5. 1 4
  6. 2 4
  7. 3 2
  8. 3 5
  9. 1 2
  10. 4 5
复制代码

输出样例
  1. 4
  2. 4
  3. 1
  4. 4
  5. 4
复制代码


样例解释

                               
登录/注册后可看大图

第一次询问：2,4 的最近公共祖先，故为 4
第二次询问：3,2的最近公共祖先，故为 4
第三次询问：3,5 的最近公共祖先，故为 1
第四次询问：1,2 的最近公共祖先，故为 4
第五次询问：4,5 的最近公共祖先，故为 4

故输出依次为 4,4,1,4,4。

数据范围
对于 70% 的数据，保证 1 <= n, m <= 10000
对于 100% 的数据，保证 1 <= n, m <= 500000，1 <= x, y, a, b <= n, 但可能存在 a = b



                               
登录/注册后可看大图


注：该题非原创，改编于：https://www.luogu.com.cn/problem/P3379


                               
登录/注册后可看大图


答案与解析
游客，如果您要查看本帖隐藏内容请回复
[/hide]

最佳战士排行榜
第一名第二名第三名
名字dolly_yos2ExiaGN001
链接戳我戳我
语言C++C++
代码得分10070
奖励5鱼币5荣誉+“最佳答案”3鱼币3荣誉2鱼币2荣誉


我们一起来 Hack

Hack 规则
1. Hack 经证实均有奖励，你在 Hack 时得提供完整证据、证明;
2. 在本关，仅支持标程 Hack，细节问题奖励 2~5 鱼币，重点问题奖励 5~10 鱼币
3. 奖励上限为 3 次


名字等待着Hack大佬~
Hack 类型
是否证实
链接
奖励


答题/奖励规则
1. 不能抄题解，否则无奖励，可能还会扣分;
2. 当您遇到问题时，您可以回贴提问，我会为您解答
3. 提供完整能得分的题解，均有奖励。
4. 因为额度原因，部分鱼油可能下一天才能奖励。


                               
登录/注册后可看大图


下一关：待更新

创作不易，如果你喜欢，别忘了评分、顶


本关满意度调查
最佳答案
月排行榜 / 总排行榜
dolly_yos2
2023-2-19 13:41:53
试逝
  1. #include <stdio.h>
  2. #include <stdbool.h>
  3. struct edge{
  4.     unsigned int to;
  5.     unsigned int next;
  6. };
  7. struct node{
  8.     unsigned int edge;
  9.     unsigned int parent;
  10.     unsigned int heir;
  11.     unsigned int size;
  12.     unsigned int depth;
  13.     unsigned int leader;
  14.     bool visited;
  15. };
  16. enum{ MaximumNode = 500001 };
  17. struct edge edges[MaximumNode << 1];
  18. struct node nodes[MaximumNode];
  19. void dfs(unsigned int target){
  20.     struct node* current = nodes + target;
  21.     current->size = 1;
  22.     current->heir = 0;
  23.     unsigned int edge = current->edge;
  24.     current->edge = -1;
  25.     while(edge != (unsigned int)-1){
  26.         unsigned int next = edges[edge].to;
  27.         struct node* next_node = nodes + next;
  28.         unsigned int next_edge = edges[edge].next;
  29.         if(!next_node->visited){
  30.             next_node->depth = current->depth + 1;
  31.             next_node->visited = true;
  32.             next_node->parent = target;
  33.             dfs(next);
  34.             current->size += next_node->size;
  35.             if(current->heir == 0 || nodes[current->heir].size < nodes[next].size){
  36.                 current->heir = next;
  37.             }
  38.             edges[edge].next = current->edge;
  39.             current->edge = edge;
  40.         }
  41.         edge = next_edge;
  42.     }
  43. }
  44. void generate(unsigned int target){
  45.     struct node* current = nodes + target;
  46.     if(current->heir != 0){
  47.         nodes[current->heir].leader = current->leader;
  48.         generate(current->heir);
  49.     }
  50.     unsigned int edge = current->edge;
  51.     while(edge != (unsigned int)-1){
  52.         if(edges[edge].to != current->heir){
  53.             nodes[edges[edge].to].leader = edges[edge].to;
  54.             generate(edges[edge].to);
  55.         }
  56.         edge = edges[edge].next;
  57.     }
  58. }
  59. void build_tree(unsigned int root){
  60.     nodes[root].depth = 0;
  61.     nodes[root].visited = true;
  62.     nodes[root].parent = 0;
  63.     dfs(root);
  64. }
  65. void generate_tree(unsigned int root){
  66.     nodes[root].leader = root;
  67.     generate(root);
  68. }
  69. unsigned int lca(unsigned int x, unsigned int y){
  70.     while(nodes[x].leader != nodes[y].leader){
  71.         if(nodes[nodes[x].leader].depth < nodes[nodes[y].leader].depth){
  72.             x ^= y;
  73.             y ^= x;
  74.             x ^= y;
  75.         }
  76.         x = nodes[nodes[x].leader].parent;
  77.     }
  78.     return nodes[x].depth > nodes[y].depth ? y : x;
  79. }
  80. int main(){
  81.     unsigned int n, s, m;
  82.     scanf("%u%u%u", &n, &m, &s);
  83.     for(unsigned int i = 1; i <= n; i++) nodes[i].edge = -1;
  84.     unsigned int x, y;
  85.     for(unsigned int i = 1, current_edge = 0; i < n; i++, current_edge++){
  86.         scanf("%u%u", &x, &y);
  87.         edges[current_edge].to = y;
  88.         edges[current_edge].next = nodes[x].edge;
  89.         nodes[x].edge = current_edge++;
  90.         edges[current_edge].to = x;
  91.         edges[current_edge].next = nodes[y].edge;
  92.         nodes[y].edge = current_edge;
  93.     }
  94.     build_tree(s);
  95.     generate_tree(s);
  96.     for(unsigned int i = 0; i < m; i++){
  97.         scanf("%u%u", &x, &y);
  98.         printf("%u\n", lca(x, y));
  99.     }
  100.     return 0;
  101. }
复制代码
多选投票: ( 最多可选 6 项 ), 共有 4 人参与投票
您所在的用户组没有投票权限

评分

参与人数 1鱼币 +1 收起 理由
myd0313 + 1 这有什么难的

查看全部评分

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

ExiaGN001
发表于 2023-2-19 11:23:32 | 显示全部楼层
本帖最后由 ExiaGN001 于 2023-2-19 11:24 编辑

暴力做会TLE的
暴力代码(吸氧70pts)
  1. #include<bits/stdc++.h>
  2. //#pragma GCC optimize(2)
  3. using namespace std;
  4. int r[500005];
  5. vector<int> e2[500005];
  6. int e[500005];
  7. int ans;int n,m,s;
  8. void dfs2(int num,int type)
  9. {
  10.         if(type==1&&r[num]==1)
  11.         {
  12.                 ans=num;
  13.                 return ;
  14.         }
  15.         if(type==0)
  16.         {
  17.                 r[num]=1;
  18.                 if(num!=s)
  19.                 dfs2(e[num],type);
  20.         }
  21.         if(type==1)
  22.         {
  23.                 if(num!=s)
  24.                 dfs2(e[num],type);
  25.         }

  27. }
  28. void dfs(int num,int f)
  29. {
  30.         e[num]=f;
  31.         int v;
  32.         for(int i=0;i<e2[num].size();i++)
  33.         {
  34.                 v=e2[num][i];
  35.                 if(v!=f)
  36.                         dfs(v,num);
  37.         }

  39. }
  40. int main()
  41. {
  42.         ios::sync_with_stdio(0);
  43.         cin.tie(0);
  44.         cout.tie(0);

  46.         cin>>n>>m>>s;
  47.         for(int i=1;i<n;i++)
  48.         {
  49.                 int x,y;
  50.                 cin>>x>>y;
  51.                 e2[y].push_back(x);
  52.                 e2[x].push_back(y);
  53.         }
  54.         dfs(s,0);//重新建树
  55.         while(m--)
  56.         {
  57.                 int x,y;
  58.                 cin>>x>>y;
  59.                 if(y==x){cout<<x<<"\n";continue;}

  61.                 memset(r,0,sizeof(r));
  62.                 dfs2(x,0);
  63.                 dfs2(y,1);
  64.                 cout<<ans<<"\n";
  65.         }

  67. }
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zhangjinxuan + 5 + 5 鱼C有你更精彩^_^

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2023-2-19 11:53:30 | 显示全部楼层
ExiaGN001 发表于 2023-2-19 11:23
暴力做会TLE的
暴力代码(吸氧70pts)


满分才会有最佳答案哦

写个倍增吧，也费不了多少

评分

参与人数 1鱼币 +1 收起 理由
myd0313 + 1 无条件支持楼主！

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

梦想护卫舰官方
发表于 2023-2-19 12:28:42 | 显示全部楼层
这不就是模板题——倍增lca 吗

评分

参与人数 1荣誉 +1 收起 理由
myd0313 + 1 无条件支持楼主！

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

sfqxx
发表于 2023-2-19 12:47:21 From FishC Mobile | 显示全部楼层
666
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

dolly_yos2
发表于 2023-2-19 13:41:53 | 显示全部楼层    本楼为最佳答案   
试逝
  1. #include <stdio.h>
  2. #include <stdbool.h>
  3. struct edge{
  4.     unsigned int to;
  5.     unsigned int next;
  6. };
  7. struct node{
  8.     unsigned int edge;
  9.     unsigned int parent;
  10.     unsigned int heir;
  11.     unsigned int size;
  12.     unsigned int depth;
  13.     unsigned int leader;
  14.     bool visited;
  15. };
  16. enum{ MaximumNode = 500001 };
  17. struct edge edges[MaximumNode << 1];
  18. struct node nodes[MaximumNode];
  19. void dfs(unsigned int target){
  20.     struct node* current = nodes + target;
  21.     current->size = 1;
  22.     current->heir = 0;
  23.     unsigned int edge = current->edge;
  24.     current->edge = -1;
  25.     while(edge != (unsigned int)-1){
  26.         unsigned int next = edges[edge].to;
  27.         struct node* next_node = nodes + next;
  28.         unsigned int next_edge = edges[edge].next;
  29.         if(!next_node->visited){
  30.             next_node->depth = current->depth + 1;
  31.             next_node->visited = true;
  32.             next_node->parent = target;
  33.             dfs(next);
  34.             current->size += next_node->size;
  35.             if(current->heir == 0 || nodes[current->heir].size < nodes[next].size){
  36.                 current->heir = next;
  37.             }
  38.             edges[edge].next = current->edge;
  39.             current->edge = edge;
  40.         }
  41.         edge = next_edge;
  42.     }
  43. }
  44. void generate(unsigned int target){
  45.     struct node* current = nodes + target;
  46.     if(current->heir != 0){
  47.         nodes[current->heir].leader = current->leader;
  48.         generate(current->heir);
  49.     }
  50.     unsigned int edge = current->edge;
  51.     while(edge != (unsigned int)-1){
  52.         if(edges[edge].to != current->heir){
  53.             nodes[edges[edge].to].leader = edges[edge].to;
  54.             generate(edges[edge].to);
  55.         }
  56.         edge = edges[edge].next;
  57.     }
  58. }
  59. void build_tree(unsigned int root){
  60.     nodes[root].depth = 0;
  61.     nodes[root].visited = true;
  62.     nodes[root].parent = 0;
  63.     dfs(root);
  64. }
  65. void generate_tree(unsigned int root){
  66.     nodes[root].leader = root;
  67.     generate(root);
  68. }
  69. unsigned int lca(unsigned int x, unsigned int y){
  70.     while(nodes[x].leader != nodes[y].leader){
  71.         if(nodes[nodes[x].leader].depth < nodes[nodes[y].leader].depth){
  72.             x ^= y;
  73.             y ^= x;
  74.             x ^= y;
  75.         }
  76.         x = nodes[nodes[x].leader].parent;
  77.     }
  78.     return nodes[x].depth > nodes[y].depth ? y : x;
  79. }
  80. int main(){
  81.     unsigned int n, s, m;
  82.     scanf("%u%u%u", &n, &m, &s);
  83.     for(unsigned int i = 1; i <= n; i++) nodes[i].edge = -1;
  84.     unsigned int x, y;
  85.     for(unsigned int i = 1, current_edge = 0; i < n; i++, current_edge++){
  86.         scanf("%u%u", &x, &y);
  87.         edges[current_edge].to = y;
  88.         edges[current_edge].next = nodes[x].edge;
  89.         nodes[x].edge = current_edge++;
  90.         edges[current_edge].to = x;
  91.         edges[current_edge].next = nodes[y].edge;
  92.         nodes[y].edge = current_edge;
  93.     }
  94.     build_tree(s);
  95.     generate_tree(s);
  96.     for(unsigned int i = 0; i < m; i++){
  97.         scanf("%u%u", &x, &y);
  98.         printf("%u\n", lca(x, y));
  99.     }
  100.     return 0;
  101. }
复制代码

评分

参与人数 1荣誉 +5 收起 理由
zhangjinxuan + 5

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2023-2-19 14:13:04 | 显示全部楼层
dolly_yos2 发表于 2023-2-19 13:41
试逝

可以，通过
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

dolly_yos2
发表于 2023-2-19 14:34:09 | 显示全部楼层
zhangjinxuan 发表于 2023-2-19 14:13
可以，通过

所以我们既不需要暴力也不需要倍增（笑）

评分

参与人数 1鱼币 +5 收起 理由
zhangjinxuan + 5 感谢楼主无私奉献！

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2023-2-19 14:37:08 | 显示全部楼层
dolly_yos2 发表于 2023-2-19 14:34
所以我们既不需要暴力也不需要倍增（笑）

我*，这是啥
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

落花盈满绣！
发表于 2023-2-24 22:50:24 | 显示全部楼层
1
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

元豪
发表于 2023-2-26 14:16:23 | 显示全部楼层
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

hveagle
发表于 2023-3-7 19:10:18 | 显示全部楼层
我和zhangjinxuan可能有亲戚关系（姓：张）
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2023-3-7 19:12:06 | 显示全部楼层
hveagle 发表于 2023-3-7 19:10
我和zhangjinxuan可能有亲戚关系（姓：张）


我们不是都有一个祖先么，猿猴，呜呜啊啊

或者同一个细胞分裂成的

但要说最近的公共祖先，嗯，不好说
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

hveagle
发表于 2023-3-7 19:13:54 | 显示全部楼层
zhangjinxuan 发表于 2023-3-7 19:12
我们不是都有一个祖先么，猿猴，呜呜啊啊

或者同一个细胞分裂成的

最近是张居正
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2023-3-7 19:14:47 | 显示全部楼层
hveagle 发表于 2023-3-7 19:13
最近是张居正

啊额哈

你把我帖子所有选项都给选了
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

hveagle
发表于 2023-3-7 19:15:45 | 显示全部楼层
zhangjinxuan 发表于 2023-3-7 19:14
啊额哈

你把我帖子所有选项都给选了

评分

参与人数 1荣誉 +3 收起 理由
zhangjinxuan + 3 你肝嘛~哎哟~

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-4-22 14:50

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表