|
|
本帖最后由 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 之间的距离。
输入样例10
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6
输出样例
数据范围
对于全部的测试点，保证 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为其它方面，每一类只能选一种，希望大家好好投票，感谢大家的支持！）
什么花里胡哨的 #ifdef __STDC_NO_VLA__
#error "VLA is required"
#endif
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#define getHH(x) ((x)>>24)
#define setHH(x,v) ((x)=((x)&0x00ffffffu)|((v)<<24))
#define getHL(x) (((x)>>16)&0xffu)
#define setHL(x,v) ((x)=((x)&0xff00ffffu)|((v)<<16))
#define getLH(x) (((x)>>8)&0xffu)
#define setLH(x,v) ((x)=((x)&0xffff00ffu)|((v)<<8))
#define getLL(x) ((x)&0xffu)
#define setLL(x,v) ((x)=((x)&0xffffff00u)|(v))
uint32_t dfs(
uint32_t* tree,
unsigned int current, unsigned int depth, unsigned int parent,
unsigned int u, unsigned int v,
unsigned int* max_depth, unsigned int* max_width
){
unsigned int current_index = current - 1;
unsigned int target;
uint32_t origin_tree = tree[current_index] & 0xffffff00u;
uint32_t formatted_tree = 0u;
while(1){
target = getHH(origin_tree);
if(!target) break;
if(target != parent){
formatted_tree >>= 8;
setHH(formatted_tree, target);
}
origin_tree <<= 8;
}
tree[current_index] = (tree[current_index] & 0xffu) | (formatted_tree & 0xffffff00u);
unsigned int width = getLL(tree[depth - 1]) + 1;
setLL(tree[depth - 1], width);
*max_width = *max_width < width ? width : *max_width;
*max_depth = *max_depth < depth ? depth : *max_depth;
uint32_t result = 0u;
if((target = getHH(formatted_tree))){
result |= dfs(tree, target, depth + 1, current, u, v, max_depth, max_width);
}
if((target = getHL(formatted_tree))){
result |= dfs(tree, target, depth + 1, current, u, v, max_depth, max_width);
}
if(current == u){
result |= 0x1u;
setHL(result, depth);
}else if(current == v){
result |= 0x2u;
setHH(result, depth);
}
if((result & 0x7u) == 0x3u){
result |= 0x4u;
setLH(result, ((getHL(result) - depth) << 1) + (getHH(result) - depth));
}
return result;
}
int main(){
int n;
scanf("%d", &n);
uint32_t tree[n];
memset(tree, 0, sizeof(tree));
unsigned int u, v;
for(int i = 1; i < n; ++i){
scanf("%u%u", &u, &v);
tree[u - 1] >>= 8;
tree[v - 1] >>= 8;
setHH(tree[u - 1], v);
setHH(tree[v - 1], u);
}
scanf("%u%u", &u, &v);
unsigned int max_depth = 0u;
unsigned int max_width = 0u;
unsigned int result = dfs(tree, 1u, 1u, 0u, u, v, &max_depth, &max_width);
printf("%u\n%u\n%u", max_depth, max_width, getLH(result));
return 0;
}
|
评分
-
| 参与人数 2 | 荣誉 +7 |
鱼币 +7 |
贡献 +3 |
收起
理由
|
 高山
| + 5 |
+ 5 |
+ 3 |
鱼C有你更精彩^_^ |
 元豪
| + 2 |
+ 2 |
|
鱼C有你更精彩^_^ |
查看全部评分
|
[复制链接]
抢楼
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2022-11-5 09:35:19
置顶卡
千斤顶
显身卡
楼主
发表于 2022-11-5 13:12:57
打