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

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › C\C++交流 › 【C++板块提升计划】每周一练 第13期 二叉树问题【回贴 ...
1234下一页
返回列表 发新帖
查看: 5303|回复: 64

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

 关闭 [复制链接]
抢楼 抢楼 查看抢中楼层 本帖为抢楼帖，鱼币大于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 
zhangjinxuan
发表于 2022-11-5 09:35:19 | 显示全部楼层 |阅读模式
本帖最后由 zhangjinxuan 于 2022-11-14 12:21 编辑

每周一练 第13期 二叉树问题



互凉网的广大盆友们，大家好，我是zhangjinxuan，

本周（第13周）的每周一练由我帮助用户 @高山 发帖

大家也看见了吧，这一期的每周一练帖子的主题分类居然是问题求助

为什么呢？是因为我们每周一练为了起到这个“练”的作用，决定使用”求助帖“的形式发布，这样才能起到”练“的作用嘛~

所以，本期如果在回复区中经行答题，发表自己的代码，并且可以AC(通过)，是有奖励的哦~

具体是什么规则可以见后面的 答题规则、奖励规则

好了，我们先进入正题 ^_^


                               
登录/注册后可看大图



题面

题目描述

假设有一棵二叉树：

                               
登录/注册后可看大图


其中，宽度及结点间距离分别为：
——深度：4
——宽度：4
——结点 8 和 6 之间的距离：8
——结点 7 和 6 之间的距离：3

在这里，宽度表示二叉树上同一深度最多的结点个数，节点 u, v之间的距离表示从 u 到 v 的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。

给定一颗以 1 号结点为根的二叉树，请求出其深度、宽度和两个指定节点 x, y 之间的距离。

输入格式

第一行是一个整数，表示树的结点个数 n。

接下来 n - 1 行，每行两个整数 u, v表示树上存在一条连接 u, v 的边。
最后一行有两个整数 x, y表示求 x, y 之间的距离。

输出格式

输入三行，每行一个整数，依次表示二叉树的深度、宽度和 x, y 之间的距离。

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


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


数据范围
对于全部的测试点，保证 1 ≤ u, v, x, y ≤ n ≤ 100，且给出的是一棵二叉树。

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


                               
登录/注册后可看大图


注意：请先独立思考，再查看解析！

参考题解
游客，如果您要查看本帖隐藏内容请回复
[/hide]

至此，代码就真的写完了


                               
登录/注册后可看大图


完整参考代码
游客，如果您要查看本帖隐藏内容请回复
[/hide]

总结
游客，如果您要查看本帖隐藏内容请回复
[/hide]


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

                               
登录/注册后可看大图


答题规则

如果你要经行答题，请遵守以下规则：
1. 不可以先发回帖，再做题，直接发你的题解，否则无奖励；
2. 不能抄题解，否则无奖励;
3. 建议使用C++或C语言来做，否则奖励会打点折扣(你看看板块，就知道该用什么语言来做了);
4. 不能通过的代码，视为普通回帖，不会奖励。

奖励规则（奖励45天内有效）
1. 代码效率最优，选为最佳答案，并置项（15天以内）;
2. 提供新的思路（加上代码），奖励 1 ~ 2 鱼币;
3. 提供新的写法（思路可以一样），奖励 1 ~ 2 荣誉;
4. 修正帖子错误，并提出解决方案，奖励1 ~ 2荣誉、1 ~ 2鱼币并且置项;
5. 其余情况，在不违反答题规则的情况下，奖励 1 荣誉；
6. 因为额度原因，部分鱼油可能下一天才能奖励。


                               
登录/注册后可看大图


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

上一篇：鱼C生活小游戏
下一篇：汉诺塔问题

这还没结束，本期还要进行本期 每周一练 的满意度调查，希望大家投票，你们的投票对我们很有帮助！

本期满意度调查
（1、2、3为题目难度满意度，4、5为题解满意度、6、7为排版满意度，8、9为其它方面，每一类只能选一种，希望大家好好投票，感谢大家的支持！）
最佳答案
月排行榜 / 总排行榜
dolly_yos2
2022-11-5 13:32:19
什么花里胡哨的
  1. #ifdef __STDC_NO_VLA__
  2.     #error "VLA is required"
  3. #endif
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <stdint.h>
  7. #include <string.h>
  8. #define getHH(x) ((x)>>24)
  9. #define setHH(x,v) ((x)=((x)&0x00ffffffu)|((v)<<24))
  10. #define getHL(x) (((x)>>16)&0xffu)
  11. #define setHL(x,v) ((x)=((x)&0xff00ffffu)|((v)<<16))
  12. #define getLH(x) (((x)>>8)&0xffu)
  13. #define setLH(x,v) ((x)=((x)&0xffff00ffu)|((v)<<8))
  14. #define getLL(x) ((x)&0xffu)
  15. #define setLL(x,v) ((x)=((x)&0xffffff00u)|(v))
  16. uint32_t dfs(
  17.     uint32_t* tree,
  18.     unsigned int current, unsigned int depth, unsigned int parent,
  19.     unsigned int u, unsigned int v,
  20.     unsigned int* max_depth, unsigned int* max_width
  21. ){
  22.     unsigned int current_index = current - 1;
  23.     unsigned int target;
  24.     uint32_t origin_tree = tree[current_index] & 0xffffff00u;
  25.     uint32_t formatted_tree = 0u;
  26.     while(1){
  27.         target = getHH(origin_tree);
  28.         if(!target) break;
  29.         if(target != parent){
  30.             formatted_tree >>= 8;
  31.             setHH(formatted_tree, target);
  32.         }
  33.         origin_tree <<= 8;
  34.     }
  35.     tree[current_index] = (tree[current_index] & 0xffu) | (formatted_tree & 0xffffff00u);
  36.     unsigned int width = getLL(tree[depth - 1]) + 1;
  37.     setLL(tree[depth - 1], width);
  38.     *max_width = *max_width < width ? width : *max_width;
  39.     *max_depth = *max_depth < depth ? depth : *max_depth;
  40.     uint32_t result = 0u;
  41.     if((target = getHH(formatted_tree))){
  42.         result |= dfs(tree, target, depth + 1, current, u, v, max_depth, max_width);
  43.     }
  44.     if((target = getHL(formatted_tree))){
  45.         result |= dfs(tree, target, depth + 1, current, u, v, max_depth, max_width);
  46.     }
  47.     if(current == u){
  48.         result |= 0x1u;
  49.         setHL(result, depth);
  50.     }else if(current == v){
  51.         result |= 0x2u;
  52.         setHH(result, depth);
  53.     }
  54.     if((result & 0x7u) == 0x3u){
  55.         result |= 0x4u;
  56.         setLH(result, ((getHL(result) - depth) << 1) + (getHH(result) - depth));
  57.     }
  58.     return result;
  59. }
  60. int main(){
  61.     int n;
  62.     scanf("%d", &n);
  63.     uint32_t tree[n];
  64.     memset(tree, 0, sizeof(tree));
  65.     unsigned int u, v;
  66.     for(int i = 1; i < n; ++i){
  67.         scanf("%u%u", &u, &v);
  68.         tree[u - 1] >>= 8;
  69.         tree[v - 1] >>= 8;
  70.         setHH(tree[u - 1], v);
  71.         setHH(tree[v - 1], u);
  72.     }
  73.     scanf("%u%u", &u, &v);
  74.     unsigned int max_depth = 0u;
  75.     unsigned int max_width = 0u;
  76.     unsigned int result = dfs(tree, 1u, 1u, 0u, u, v, &max_depth, &max_width);
  77.     printf("%u\n%u\n%u", max_depth, max_width, getLH(result));
  78.     return 0;
  79. }
复制代码
多选投票: ( 最多可选 4 项 ), 共有 6 人参与投票
您所在的用户组没有投票权限

评分

参与人数 2荣誉 +7 鱼币 +7 贡献 +3 收起 理由
高山 + 5 + 5 + 3 鱼C有你更精彩^_^
元豪 + 2 + 2 鱼C有你更精彩^_^

查看全部评分

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

dolly_yos2
发表于 2022-11-5 13:32:19 | 显示全部楼层    本楼为最佳答案   

回帖奖励 +2 鱼币

什么花里胡哨的
  1. #ifdef __STDC_NO_VLA__
  2.     #error "VLA is required"
  3. #endif
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <stdint.h>
  7. #include <string.h>
  8. #define getHH(x) ((x)>>24)
  9. #define setHH(x,v) ((x)=((x)&0x00ffffffu)|((v)<<24))
  10. #define getHL(x) (((x)>>16)&0xffu)
  11. #define setHL(x,v) ((x)=((x)&0xff00ffffu)|((v)<<16))
  12. #define getLH(x) (((x)>>8)&0xffu)
  13. #define setLH(x,v) ((x)=((x)&0xffff00ffu)|((v)<<8))
  14. #define getLL(x) ((x)&0xffu)
  15. #define setLL(x,v) ((x)=((x)&0xffffff00u)|(v))
  16. uint32_t dfs(
  17.     uint32_t* tree,
  18.     unsigned int current, unsigned int depth, unsigned int parent,
  19.     unsigned int u, unsigned int v,
  20.     unsigned int* max_depth, unsigned int* max_width
  21. ){
  22.     unsigned int current_index = current - 1;
  23.     unsigned int target;
  24.     uint32_t origin_tree = tree[current_index] & 0xffffff00u;
  25.     uint32_t formatted_tree = 0u;
  26.     while(1){
  27.         target = getHH(origin_tree);
  28.         if(!target) break;
  29.         if(target != parent){
  30.             formatted_tree >>= 8;
  31.             setHH(formatted_tree, target);
  32.         }
  33.         origin_tree <<= 8;
  34.     }
  35.     tree[current_index] = (tree[current_index] & 0xffu) | (formatted_tree & 0xffffff00u);
  36.     unsigned int width = getLL(tree[depth - 1]) + 1;
  37.     setLL(tree[depth - 1], width);
  38.     *max_width = *max_width < width ? width : *max_width;
  39.     *max_depth = *max_depth < depth ? depth : *max_depth;
  40.     uint32_t result = 0u;
  41.     if((target = getHH(formatted_tree))){
  42.         result |= dfs(tree, target, depth + 1, current, u, v, max_depth, max_width);
  43.     }
  44.     if((target = getHL(formatted_tree))){
  45.         result |= dfs(tree, target, depth + 1, current, u, v, max_depth, max_width);
  46.     }
  47.     if(current == u){
  48.         result |= 0x1u;
  49.         setHL(result, depth);
  50.     }else if(current == v){
  51.         result |= 0x2u;
  52.         setHH(result, depth);
  53.     }
  54.     if((result & 0x7u) == 0x3u){
  55.         result |= 0x4u;
  56.         setLH(result, ((getHL(result) - depth) << 1) + (getHH(result) - depth));
  57.     }
  58.     return result;
  59. }
  60. int main(){
  61.     int n;
  62.     scanf("%d", &n);
  63.     uint32_t tree[n];
  64.     memset(tree, 0, sizeof(tree));
  65.     unsigned int u, v;
  66.     for(int i = 1; i < n; ++i){
  67.         scanf("%u%u", &u, &v);
  68.         tree[u - 1] >>= 8;
  69.         tree[v - 1] >>= 8;
  70.         setHH(tree[u - 1], v);
  71.         setHH(tree[v - 1], u);
  72.     }
  73.     scanf("%u%u", &u, &v);
  74.     unsigned int max_depth = 0u;
  75.     unsigned int max_width = 0u;
  76.     unsigned int result = dfs(tree, 1u, 1u, 0u, u, v, &max_depth, &max_width);
  77.     printf("%u\n%u\n%u", max_depth, max_width, getLH(result));
  78.     return 0;
  79. }
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
zhangjinxuan + 1 + 1 用时和我一样！感谢写代码！

查看全部评分

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2022-11-5 09:36:46 | 显示全部楼层
@人造人 @不二如是 @tommyyu @jackz007 创作不易，求顶
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2022-11-5 10:06:15 | 显示全部楼层
不是，这题很难吗？怎么到现在都这么冷清
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2022-11-5 10:26:08 | 显示全部楼层
啊，我辛辛苦苦做这么久，这这这....
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2022-11-5 10:37:59 | 显示全部楼层
创作真的不易，求一个小小的评分和顶，感谢
@柿子饼同学 @元豪 @Twilight6 @小凯2013
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2022-11-5 10:38:31 | 显示全部楼层
没AT上？？？
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2022-11-5 11:13:09 | 显示全部楼层
不行，增大一点回帖奖励
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2022-11-5 11:32:12 | 显示全部楼层
是不是题目太难了？
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2022-11-5 11:32:59 | 显示全部楼层
算了，任这个帖子自生自灭吧，这也太冷清了
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

人造人
发表于 2022-11-5 13:12:57 | 显示全部楼层
zhangjinxuan 发表于 2022-11-5 11:32
算了，任这个帖子自生自灭吧，这也太冷清了

^_^
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2022-11-5 13:13:33 From FishC Mobile | 显示全部楼层
本帖最后由 zhangjinxuan 于 2022-11-5 20:19 编辑
人造人 发表于 2022-11-5 13:12
^_^


感谢回帖
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

hveagle
发表于 2022-11-5 14:47:06 | 显示全部楼层
不打
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

hveagle
发表于 2022-11-5 14:50:15 | 显示全部楼层
求出 1 + 1 = 3...啊不，1 + 1 = 2
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

hveagle
发表于 2022-11-5 15:04:44 | 显示全部楼层
鱼币啊！

评分

参与人数 1鱼币 +2 收起 理由
zhangjinxuan + 2 我给鱼币，你给贡献，不过分吧

查看全部评分

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2022-11-5 16:09:54 | 显示全部楼层
hveagle 发表于 2022-11-5 14:47
不打

求评分，谢谢
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2022-11-5 16:11:58 | 显示全部楼层
hveagle 发表于 2022-11-5 14:50
求出 1 + 1 = 3...啊不，1 + 1 = 2

我调大了概率，现在在试试？
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

高山
发表于 2022-11-5 16:59:57 | 显示全部楼层

回帖奖励 +2 鱼币

第x期？？
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

zhangjinxuan
 楼主| 发表于 2022-11-5 17:43:49 | 显示全部楼层
高山 发表于 2022-11-5 16:59
第x期？？

啊！现在才发现，感谢
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

元豪
发表于 2022-11-5 18:13:59 | 显示全部楼层

回帖奖励 +2 鱼币

来
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-5-13 08:31

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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