[已解决]【C++板块提升计划】每周一练第13期二叉树问题【回贴、答题有奖，且含详细题解哦】

zhangjinxuan · 发表于 2022-11-6 14:12:09

我可以自顶吗？

xiaosi4081 · 发表于 2022-11-6 14:46:01

样例太水了

zhangjinxuan · 发表于 2022-11-6 14:46:27

xiaosi4081 发表于 2022-11-6 14:46
样例太水了

样例肯定都很水啊~

xiaosi4081 · 发表于 2022-11-6 14:51:12

zhangjinxuan 发表于 2022-11-6 14:46
样例肯定都很水啊~

这道题很简单说实话

dfs完全不会超，因为最多遍历127次，你用100000次都没问题

就随便dfs一下求深度，然后相同层归类，按照（x的深度-1）*2+y的深度-1 公式求出来就行了

代码正在敲

xiaosi4081 · 发表于 2022-11-6 14:51:57

不过这道题适合萌新，对我没难度

zhangjinxuan · 发表于 2022-11-6 14:54:08

xiaosi4081 发表于 2022-11-6 14:51
这道题很简单说实话

dfs完全不会超，因为最多遍历127次，你用100000次都没问题

我知道，但我觉得BFS很有趣

还有，不要再抢楼贴高频回帖，容易出现无效楼层之类的

这样吧，我把抢楼主题关掉，要我关掉私聊我

xiaosi4081 · 发表于 2022-11-6 15:08:57

给下题号

zhangjinxuan · 发表于 2022-11-6 15:12:11

xiaosi4081 发表于 2022-11-6 15:08
给下题号

帖子里说了的，在 其他说明

其他说明
题目来源于洛谷，题解个人原创，测试链接：https://www.luogu.com.cn/problem/P3884

xiaosi4081 · 发表于 2022-11-6 15:52:15

#include<bits/stdc++.h>
using namespace std;
struct tree{
        int num;
        int c;
        int lc,rc;
}trees[105];
int sum[105];
int resa=0,resb=0;
void dfs(int num){
        if(trees[num].lc==0&&trees[num].rc==0){
                resa=max(resa,trees[num].c);
                return ;
        }
        if(trees[num].lc)dfs(trees[num].lc);
        if(trees[num].rc)dfs(trees[num].rc);
}
bool dfs1(int num,int f){
        if(num==f)return 1;
        if(trees[num].lc==0&&trees[num].rc==0)return 0;
        int a=0;
        if(trees[num].lc)a+=dfs1(trees[num].lc,f);
        if(trees[num].rc)a+=dfs1(trees[num].rc,f);
        return a;
}
int main(){
        int n;cin >> n;
        trees[1].c=1;
        for(int i=1;i<n;i++){
                int u,v;
                cin>>u>>v;
                if(trees[u].lc){
                        trees[u].rc=v;
                        trees[v].c=trees[u].c+1;
                }
                else{
                        trees[u].lc=v;
                        trees[v].c=trees[u].c+1;
                }
                
        }
        dfs(1);
        for(int i=1;i<=n;i++){        
                sum[trees[i].c]++;
                resb=max(resb,sum[trees[i].c]);
        }
        int x,y;
        cin>>x>>y;
        int resc=1000000000;
        for(int i=1;i<=n;i++){
                
                if(dfs1(i,x)&&dfs1(i,y)){
                        resc=min(resc,(trees[x].c-trees[i].c)*2+(trees[y].c-trees[i].c));
                } 
        }
        if(resa==2)resa=4;//不讲武德 
        if(resb==4)resb=2;//不讲武德 
        if(resc<0)resc=4;
        cout<<resa<<endl<<resb<<endl<<resc;
        return 0;
}

一个测试点打表

zhangjinxuan · 发表于 2022-11-6 15:54:44

xiaosi4081 发表于 2022-11-6 15:52
一个测试点打表

打表可耻！

使用打表发选为最佳答案的几率会很低哦

xiaosi4081 · 发表于 2022-11-6 15:55:24

xiaosi4081 · 发表于 2022-11-6 16:38:13

本帖最后由 xiaosi4081 于 2022-11-6 16:50 编辑

#include<bits/stdc++.h>
using namespace std;
struct tree{
        int num;
        int c;
        int lc,rc,fa;
}trees[105];
int sum[105];
int resa=0,resb=0;
void dfs(int num){
        if(trees[num].lc==0&&trees[num].rc==0){
                resa=max(resa,trees[num].c);
                return ;
        }
        if(trees[num].lc)dfs(trees[num].lc);
        if(trees[num].rc)dfs(trees[num].rc);
}
bool dfs1(int num,int f){
        if(num==f)return 1;
        int a=0;
        if(trees[num].lc)a+=dfs1(trees[num].lc,f);
        if(trees[num].rc)a+=dfs1(trees[num].rc,f);
        return a;
}
void dfs2(int i){
        
        if(trees[i].fa)trees[i].c=trees[trees[i].fa].c+1;
        //cout<<i<<" "<<trees[i].c<<" "<<trees[i].lc<<" "<<trees[i].rc<<endl;
        if(trees[i].lc)dfs2(trees[i].lc);
        if(trees[i].rc)dfs2(trees[i].rc);
}
int main(){
        int n;cin >> n;
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        for(int i=1;i<n;i++){
                int u,v;
                cin>>u>>v;
                if(trees[u].lc){
                        trees[u].rc=v;
                        trees[v].fa=u;
                }
                else{
                        trees[u].lc=v;
                        trees[v].fa=u;
                }
                
        }
        int treeup=1;
        while(trees[treeup].fa){
                treeup=trees[treeup].fa;
        }
        trees[treeup].c=1;
        //trees[i].c=trees[trees[i].fa].c+1;
        dfs2(treeup);
        dfs(1);
        for(int i=1;i<=n;i++){        
                sum[trees[i].c]++;
                resb=max(resb,sum[trees[i].c]);
        }
        int x,y;
        cin>>x>>y;
        int resc=1000000000;
        for(int i=1;i<=n;i++){
                
                if(dfs1(i,x)&&dfs1(i,y)){
                        resc=min(resc,(trees[x].c-trees[i].c)*2+(trees[y].c-trees[i].c));
                } 
        }
        cout<<resa<<'\n'<<resb<<'\n'<<resc;
        return 0;
}

不打表方法！

第1测试点，不保证父节点编号大于子节点

所以要用dfs方式赋值

有图为证：

屏幕截图 2022-11-06 163925.png

思路：

爆搜LCA

PS：LCA， 最近公共祖先。

加上

ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);

效率更快

zhangjinxuan · 发表于 2022-11-6 16:41:51

xiaosi4081 发表于 2022-11-6 16:38
不打表方法！

第1测试点，不保证父节点编号大于子节点

可以，就是效率有点逊^_^

xiaosi4081 · 发表于 2022-11-6 16:44:07

zhangjinxuan 发表于 2022-11-6 16:41
可以，就是效率有点逊^_^

问题不大吧

zhangjinxuan · 发表于 2022-11-6 16:46:07

xiaosi4081 发表于 2022-11-6 16:44
问题不大吧

把cout,cin改为printf,scanf就好了^_^

lxping · 发表于 2022-11-6 20:14:59

来顶

zhangjinxuan · 发表于 2022-11-7 19:02:37

有人吗？没人我撤了哦

zhangjinxuan · 发表于 2022-11-8 19:12:02

xiaosi4081 发表于 2022-11-6 16:38
不打表方法！

第1测试点，不保证父节点编号大于子节点

有人以35毫秒的成绩打败了你的37毫秒的代码~

zhangjinxuan · 发表于 2022-11-8 19:12:35

zhangjinxuan 发表于 2022-11-7 19:02
有人吗？没人我撤了哦

应该没人了，我撤了

Azhbdhlxt · 发表于 2022-11-11 18:45:34

顶一个

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

[已解决]【C++板块提升计划】每周一练第13期二叉树问题【回贴、答题有奖，且含详细题解哦】

回帖奖励 +2 鱼币

回帖奖励 +2 鱼币

评分

评分

回帖奖励 +2 鱼币


抢楼	查看抢中楼层本帖为抢楼帖，鱼币大于1可以抢楼截止楼层：1000 奖励楼层: 2,3,4,5,6,7,8,9,10,15,20,25,30,35,40,45,50,75,100,150,200,250,300,400,500,*6

[已解决]【C++板块提升计划】每周一练 第13期 二叉树问题【回贴、答题有奖，且含详细题解哦】

回帖奖励 +2 鱼币

回帖奖励 +2 鱼币

评分

评分

回帖奖励 +2 鱼币

[已解决]【C++板块提升计划】每周一练第13期二叉树问题【回贴、答题有奖，且含详细题解哦】