【C++板块提升计划】梦想护卫舰第25关最近公共祖先,C\C++交流,编程语言专区,鱼C论坛

zhangjinxuan 发表于 2023-2-19 10:01:26

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

本帖最后由 zhangjinxuan 于 2023-2-19 15:21 编辑

上一关：性能测试

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

梦想护卫舰终于继续出发

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

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

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

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

输入样例
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
输出样例
4
4
1
4
4

样例解释
https://cdn.luogu.com.cn/upload/pic/2282.png
第一次询问：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

static/image/hrline/1.gif

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

static/image/hrline/1.gif

答案与解析
**** Hidden Message *****

最佳战士排行榜

|第一名|第二名|第三名
名字|dolly_yos2|ExiaGN001|
链接|戳我|戳我|
语言|C++|C++|
代码得分|100|70|
奖励|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. 因为额度原因，部分鱼油可能下一天才能奖励。

static/image/hrline/1.gif

下一关：待更新

创作不易，如果你喜欢，别忘了评分、顶{:10_281:}

本关满意度调查

ExiaGN001 发表于 2023-2-19 11:23:32

本帖最后由 ExiaGN001 于 2023-2-19 11:24 编辑

暴力做会TLE的
暴力代码(吸氧70pts)
#include<bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
int r;
vector<int> e2;
int e;
int ans;int n,m,s;
void dfs2(int num,int type)
{
if(type==1&&r==1)
{
ans=num;
return ;
}
if(type==0)
{
r=1;
if(num!=s)
dfs2(e,type);
}
if(type==1)
{
if(num!=s)
dfs2(e,type);
}

}
void dfs(int num,int f)
{
e=f;
int v;
for(int i=0;i<e2.size();i++)
{
v=e2;
if(v!=f)
dfs(v,num);
}

}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin>>n>>m>>s;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
e2.push_back(x);
e2.push_back(y);
}
dfs(s,0);//重新建树
while(m--)
{
int x,y;
cin>>x>>y;
if(y==x){cout<<x<<"\n";continue;}

memset(r,0,sizeof(r));
dfs2(x,0);
dfs2(y,1);
cout<<ans<<"\n";
}

}

zhangjinxuan 发表于 2023-2-19 11:53:30

ExiaGN001 发表于 2023-2-19 11:23
暴力做会TLE的
暴力代码(吸氧70pts)

满分才会有最佳答案哦{:10_282:}

写个倍增吧，也费不了多少{:10_256:}

梦想护卫舰官方 发表于 2023-2-19 12:28:42

这不就是模板题——倍增lca 吗

sfqxx 发表于 2023-2-19 12:47:21

666

dolly_yos2 发表于 2023-2-19 13:41:53

试逝#include <stdio.h>
#include <stdbool.h>
struct edge{
unsigned int to;
unsigned int next;
};
struct node{
unsigned int edge;
unsigned int parent;
unsigned int heir;
unsigned int size;
unsigned int depth;
unsigned int leader;
bool visited;
};
enum{ MaximumNode = 500001 };
struct edge edges;
struct node nodes;
void dfs(unsigned int target){
struct node* current = nodes + target;
current->size = 1;
current->heir = 0;
unsigned int edge = current->edge;
current->edge = -1;
while(edge != (unsigned int)-1){
   unsigned int next = edges.to;
   struct node* next_node = nodes + next;
   unsigned int next_edge = edges.next;
   if(!next_node->visited){
         next_node->depth = current->depth + 1;
         next_node->visited = true;
         next_node->parent = target;
         dfs(next);
         current->size += next_node->size;
         if(current->heir == 0 || nodes.size < nodes.size){
            current->heir = next;
         }
         edges.next = current->edge;
         current->edge = edge;
   }
   edge = next_edge;
}
}
void generate(unsigned int target){
struct node* current = nodes + target;
if(current->heir != 0){
   nodes.leader = current->leader;
   generate(current->heir);
}
unsigned int edge = current->edge;
while(edge != (unsigned int)-1){
   if(edges.to != current->heir){
         nodes.to].leader = edges.to;
         generate(edges.to);
   }
   edge = edges.next;
}
}
void build_tree(unsigned int root){
nodes.depth = 0;
nodes.visited = true;
nodes.parent = 0;
dfs(root);
}
void generate_tree(unsigned int root){
nodes.leader = root;
generate(root);
}
unsigned int lca(unsigned int x, unsigned int y){
while(nodes.leader != nodes.leader){
   if(nodes.leader].depth < nodes.leader].depth){
         x ^= y;
         y ^= x;
         x ^= y;
   }
   x = nodes.leader].parent;
}
return nodes.depth > nodes.depth ? y : x;
}
int main(){
unsigned int n, s, m;
scanf("%u%u%u", &n, &m, &s);
for(unsigned int i = 1; i <= n; i++) nodes.edge = -1;
unsigned int x, y;
for(unsigned int i = 1, current_edge = 0; i < n; i++, current_edge++){
   scanf("%u%u", &x, &y);
   edges.to = y;
   edges.next = nodes.edge;
   nodes.edge = current_edge++;
   edges.to = x;
   edges.next = nodes.edge;
   nodes.edge = current_edge;
}
build_tree(s);
generate_tree(s);
for(unsigned int i = 0; i < m; i++){
   scanf("%u%u", &x, &y);
   printf("%u\n", lca(x, y));
}
return 0;
}

zhangjinxuan 发表于 2023-2-19 14:13:04

dolly_yos2 发表于 2023-2-19 13:41
试逝

可以，通过{:10_256:}

dolly_yos2 发表于 2023-2-19 14:34:09

zhangjinxuan 发表于 2023-2-19 14:13
可以，通过

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

zhangjinxuan 发表于 2023-2-19 14:37:08

dolly_yos2 发表于 2023-2-19 14:34
所以我们既不需要暴力也不需要倍增（笑）

我*，这是啥{:10_277:}

落花盈满绣！ 发表于 2023-2-24 22:50:24

元豪发表于 2023-2-26 14:16:23

{:10_266:}

hveagle 发表于 2023-3-7 19:10:18

我和zhangjinxuan可能有亲戚关系（姓：张）

zhangjinxuan 发表于 2023-3-7 19:12:06

hveagle 发表于 2023-3-7 19:10
我和zhangjinxuan可能有亲戚关系（姓：张）

我们不是都有一个祖先么，猿猴，呜呜啊啊{:10_302:}

或者同一个细胞分裂成的{:10_256:}

但要说最近的公共祖先，嗯，不好说

hveagle 发表于 2023-3-7 19:13:54

zhangjinxuan 发表于 2023-3-7 19:12
我们不是都有一个祖先么，猿猴，呜呜啊啊

或者同一个细胞分裂成的

最近是张居正{:10_256:}

zhangjinxuan 发表于 2023-3-7 19:14:47

hveagle 发表于 2023-3-7 19:13
最近是张居正

啊{:10_277:}额{:10_257:}哈{:10_256:}

你把我帖子所有选项都给选了{:10_282:}

hveagle 发表于 2023-3-7 19:15:45

zhangjinxuan 发表于 2023-3-7 19:14
啊额哈

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

{:10_295:}

页: [1]

鱼C论坛's Archiver

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

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