【C++板块提升计划】每周一练 第13期 二叉树问题【回贴、答题有奖，且含详细题解哦】
本帖最后由 zhangjinxuan 于 2022-11-14 12:21 编辑每周一练 第13期 二叉树问题
互凉网的广大盆友们，大家好，我是zhangjinxuan，
本周（第13周）的每周一练由我帮助用户 @高山 发帖
大家也看见了吧，这一期的每周一练帖子的主题分类居然是问题求助{:10_257:}
为什么呢？是因为我们每周一练为了起到这个“练”的作用，决定使用”求助帖“的形式发布，这样才能起到”练“的作用嘛~
所以，本期如果在回复区中经行答题，发表自己的代码，并且可以AC(通过)，是有奖励的哦~
具体是什么规则可以见后面的 答题规则、奖励规则
好了，我们先进入正题 ^_^
static/image/hrline/1.gif
题面
题目描述
假设有一棵二叉树：
https://cdn.luogu.com.cn/upload/pic/6843.png
其中，宽度及结点间距离分别为：
——深度：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
输出样例
4
4
8
数据范围
对于全部的测试点，保证 1 ≤ u, v, x, y ≤ n ≤ 100，且给出的是一棵二叉树。
其他说明
题目来源于 洛谷，题解个人原创，测试链接：https://www.luogu.com.cn/problem/P3884
static/image/hrline/1.gif
注意：请先独立思考，再查看解析！
参考题解
**** Hidden Message *****
至此，代码就真的写完了{:10_298:}
static/image/hrline/1.gif
完整参考代码
**** Hidden Message *****
总结
**** Hidden Message *****
最佳答案
**** Hidden Message *****
static/image/hrline/1.gif
答题规则
如果你要经行答题，请遵守以下规则：
1. 不可以先发回帖，再做题，直接发你的题解，否则无奖励；
2. 不能抄题解，否则无奖励;
3. 建议使用C++或C语言来做，否则奖励会打点折扣(你看看板块，就知道该用什么语言来做了);
4. 不能通过的代码，视为普通回帖，不会奖励。
奖励规则（奖励45天内有效）
1. 代码效率最优，选为最佳答案，并置项（15天以内）;
2. 提供新的思路（加上代码），奖励 1 ~ 2 鱼币;
3. 提供新的写法（思路可以一样），奖励 1 ~ 2 荣誉;
4. 修正帖子错误，并提出解决方案，奖励1 ~ 2荣誉、1 ~ 2鱼币并且置项;
5. 其余情况，在不违反答题规则的情况下，奖励 1 荣誉；
6. 因为额度原因，部分鱼油可能下一天才能奖励。
static/image/hrline/1.gif
创作真的不易，如果你喜欢，别忘了评分、顶{:10_281:}
上一篇：鱼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 & 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 = (tree & 0xffu) | (formatted_tree & 0xffffff00u);
unsigned int width = getLL(tree) + 1;
setLL(tree, 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;
memset(tree, 0, sizeof(tree));
unsigned int u, v;
for(int i = 1; i < n; ++i){
scanf("%u%u", &u, &v);
tree >>= 8;
tree >>= 8;
setHH(tree, v);
setHH(tree, 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;
} @人造人 @不二如是 @tommyyu @jackz007 创作不易，求顶{:10_254:} 不是，这题很难吗？怎么到现在都这么冷清{:10_277:} 啊，我辛辛苦苦做这么久，这这这....{:10_266:} 创作真的不易，求一个小小的评分和顶，感谢{:10_254:}
@柿子饼同学 @元豪 @Twilight6 @小凯2013 没AT上？？？ 不行，增大一点回帖奖励 是不是题目太难了？ 算了，任这个帖子自生自灭吧，这也太冷清了{:10_266:} zhangjinxuan 发表于 2022-11-5 11:32
算了，任这个帖子自生自灭吧，这也太冷清了
^_^ 本帖最后由 zhangjinxuan 于 2022-11-5 20:19 编辑
人造人 发表于 2022-11-5 13:12
^_^
感谢回帖{:5_100:} 不{:7_146:}打{:10_256:} 求出 1 + 1 = 3...啊不，1 + 1 = 2 鱼币啊！ hveagle 发表于 2022-11-5 14:47
不打
求评分，谢谢{:10_254:} hveagle 发表于 2022-11-5 14:50
求出 1 + 1 = 3...啊不，1 + 1 = 2
我调大了概率，现在在试试？ 第x期？？ 高山 发表于 2022-11-5 16:59
第x期？？
啊！现在才发现，感谢 来{:7_146:}