首页 > 试题广场 >

树上节点

[编程题]树上节点

给定一棵根为1号节点的树，每个节点初始的权值为1。现在每次可以选择一个节点，使得其子树所有节点的权值加1，请问最少多少次操作可以使得每个节点的权值等于它的编号？

第一行输入一个正整数，代表树上的节点数量。
接下来的行，每行输入两个正整数和，代表号节点和号节点有一条边相连。

一个整数，代表最小的操作次数。

示例1

输入

3
1 2
1 3

第1次选择编号为2的子树。
第2次选择编号为3的子树。
第3次选择编号为3的子树。

算法知识视频讲解

Python

XXXXXXin425

n = int(input())

res = 0
for _ in range(n-1):
    a, b = list(map(int, input().split()))
    res += abs(b-a)
print(res)

父节点必须小于子节点，子节点a只需要在父节点b基础上再操作(a-b)次，直接把所有边的差的绝对值求和就行，被这题目的说法绕了好久。。。。。。。。。。。。。。。。。。。。。。。

发表于 2023-03-14 23:20:26 回复(0)

提交观点

来自：22年秋招蚂蚁编程题精选

难度：

1条回答 6收藏 1583浏览

树上节点

扫一扫，把题目装进口袋