[已解决]【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 行，每行包含一个正整数，依次为每一个询问的结果。

输入样例

输出样例

样例解释

登录/注册后可看大图

第一次询问：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_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. 因为额度原因，部分鱼油可能下一天才能奖励。

登录/注册后可看大图

下一关：待更新

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

本关满意度调查

最佳答案

月排行榜 / 总排行榜

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[MaximumNode << 1];
struct node nodes[MaximumNode];
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[edge].to;
        struct node* next_node = nodes + next;
        unsigned int next_edge = edges[edge].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[current->heir].size < nodes[next].size){
                current->heir = next;
            }
            edges[edge].next = current->edge;
            current->edge = edge;
        }
        edge = next_edge;
    }
}
void generate(unsigned int target){
    struct node* current = nodes + target;
    if(current->heir != 0){
        nodes[current->heir].leader = current->leader;
        generate(current->heir);
    }
    unsigned int edge = current->edge;
    while(edge != (unsigned int)-1){
        if(edges[edge].to != current->heir){
            nodes[edges[edge].to].leader = edges[edge].to;
            generate(edges[edge].to);
        }
        edge = edges[edge].next;
    }
}
void build_tree(unsigned int root){
    nodes[root].depth = 0;
    nodes[root].visited = true;
    nodes[root].parent = 0;
    dfs(root);
}
void generate_tree(unsigned int root){
    nodes[root].leader = root;
    generate(root);
}
unsigned int lca(unsigned int x, unsigned int y){
    while(nodes[x].leader != nodes[y].leader){
        if(nodes[nodes[x].leader].depth < nodes[nodes[y].leader].depth){
            x ^= y;
            y ^= x;
            x ^= y;
        }
        x = nodes[nodes[x].leader].parent;
    }
    return nodes[x].depth > nodes[y].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[i].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[current_edge].to = y;
        edges[current_edge].next = nodes[x].edge;
        nodes[x].edge = current_edge++;
        edges[current_edge].to = x;
        edges[current_edge].next = nodes[y].edge;
        nodes[y].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;
}

跳转到最佳答案楼层

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[500005];
vector<int> e2[500005];
int e[500005];
int ans;int n,m,s;
void dfs2(int num,int type)
{
        if(type==1&&r[num]==1)
        {
                ans=num;
                return ;
        }
        if(type==0)
        {
                r[num]=1;
                if(num!=s)
                dfs2(e[num],type);
        }
        if(type==1)
        {
                if(num!=s)
                dfs2(e[num],type);
        }

}
void dfs(int num,int f)
{
        e[num]=f;
        int v;
        for(int i=0;i<e2[num].size();i++)
        {
                v=e2[num][i];
                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[y].push_back(x);
                e2[x].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)

满分才会有最佳答案哦

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

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

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

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

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

这个最佳答案由 dolly_yos2 给出，感谢 dolly_yos2 的回答。

单击隐藏图章

试逝

#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[MaximumNode << 1];
struct node nodes[MaximumNode];
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[edge].to;
        struct node* next_node = nodes + next;
        unsigned int next_edge = edges[edge].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[current->heir].size < nodes[next].size){
                current->heir = next;
            }
            edges[edge].next = current->edge;
            current->edge = edge;
        }
        edge = next_edge;
    }
}
void generate(unsigned int target){
    struct node* current = nodes + target;
    if(current->heir != 0){
        nodes[current->heir].leader = current->leader;
        generate(current->heir);
    }
    unsigned int edge = current->edge;
    while(edge != (unsigned int)-1){
        if(edges[edge].to != current->heir){
            nodes[edges[edge].to].leader = edges[edge].to;
            generate(edges[edge].to);
        }
        edge = edges[edge].next;
    }
}
void build_tree(unsigned int root){
    nodes[root].depth = 0;
    nodes[root].visited = true;
    nodes[root].parent = 0;
    dfs(root);
}
void generate_tree(unsigned int root){
    nodes[root].leader = root;
    generate(root);
}
unsigned int lca(unsigned int x, unsigned int y){
    while(nodes[x].leader != nodes[y].leader){
        if(nodes[nodes[x].leader].depth < nodes[nodes[y].leader].depth){
            x ^= y;
            y ^= x;
            x ^= y;
        }
        x = nodes[nodes[x].leader].parent;
    }
    return nodes[x].depth > nodes[y].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[i].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[current_edge].to = y;
        edges[current_edge].next = nodes[x].edge;
        nodes[x].edge = current_edge++;
        edges[current_edge].to = x;
        edges[current_edge].next = nodes[y].edge;
        nodes[y].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
试逝

可以，通过

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
所以我们既不需要暴力也不需要倍增（笑）

我*，这是啥

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

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

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

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

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

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

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

或者同一个细胞分裂成的

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

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

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

或者同一个细胞分裂成的

账号		自动登录	找回密码
密码			立即注册

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

评分

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分

评分

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