zhangjinxuan 发表于 2022-11-5 09:35:19

【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为其它方面,每一类只能选一种,希望大家好好投票,感谢大家的支持!)

dolly_yos2 发表于 2022-11-5 13:32:19

什么花里胡哨的
#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;
}

zhangjinxuan 发表于 2022-11-5 09:36:46

@人造人 @不二如是 @tommyyu @jackz007 创作不易,求顶{:10_254:}

zhangjinxuan 发表于 2022-11-5 10:06:15

不是,这题很难吗?怎么到现在都这么冷清{:10_277:}

zhangjinxuan 发表于 2022-11-5 10:26:08

啊,我辛辛苦苦做这么久,这这这....{:10_266:}

zhangjinxuan 发表于 2022-11-5 10:37:59

创作真的不易,求一个小小的评分和顶,感谢{:10_254:}
@柿子饼同学 @元豪 @Twilight6 @小凯2013

zhangjinxuan 发表于 2022-11-5 10:38:31

没AT上???

zhangjinxuan 发表于 2022-11-5 11:13:09

不行,增大一点回帖奖励

zhangjinxuan 发表于 2022-11-5 11:32:12

是不是题目太难了?

zhangjinxuan 发表于 2022-11-5 11:32:59

算了,任这个帖子自生自灭吧,这也太冷清了{:10_266:}

人造人 发表于 2022-11-5 13:12:57

zhangjinxuan 发表于 2022-11-5 11:32
算了,任这个帖子自生自灭吧,这也太冷清了

^_^

zhangjinxuan 发表于 2022-11-5 13:13:33

本帖最后由 zhangjinxuan 于 2022-11-5 20:19 编辑

人造人 发表于 2022-11-5 13:12
^_^

感谢回帖{:5_100:}

hveagle 发表于 2022-11-5 14:47:06

不{:7_146:}打{:10_256:}

hveagle 发表于 2022-11-5 14:50:15

求出 1 + 1 = 3...啊不,1 + 1 = 2

hveagle 发表于 2022-11-5 15:04:44

鱼币啊!

zhangjinxuan 发表于 2022-11-5 16:09:54

hveagle 发表于 2022-11-5 14:47
不打

求评分,谢谢{:10_254:}

zhangjinxuan 发表于 2022-11-5 16:11:58

hveagle 发表于 2022-11-5 14:50
求出 1 + 1 = 3...啊不,1 + 1 = 2

我调大了概率,现在在试试?

高山 发表于 2022-11-5 16:59:57

第x期??

zhangjinxuan 发表于 2022-11-5 17:43:49

高山 发表于 2022-11-5 16:59
第x期??

啊!现在才发现,感谢

元豪 发表于 2022-11-5 18:13:59

来{:7_146:}
页: [1] 2 3 4
查看完整版本: 【C++板块提升计划】每周一练 第13期 二叉树问题【回贴、答题有奖,且含详细题解哦】