我要招人

去企业版

首页 > 试题广场 >

树上节点

[编程题]树上节点

热度指数：307 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵根为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)

我和小夏喝牛奶

#include <iostream>
#include <vector>
#include <list>
using namespace std;

struct Node {
    int num{1};
    list<int> child_;
    Node() = default;
};

void dfs(vector<Node>& table_ ,int root, long long& result, int father_num) {
    int select = root - father_num;
    result += select;

    table_[root].num = root;

    for (int child : table_[root].child_) {
        dfs(table_, child, result, root);
    }
}

int main() {
    int node_nums = -1;
    cin >> node_nums;

    vector<Node> table_(node_nums + 1);
    int father, chil;
    
    while (cin >> father >> chil) {
        if (chil < father) {
            std::swap(chil, father);
        }
        table_[father].child_.push_back(chil);
    }

    /////////////////////////////
    long long result = 0;

    dfs(table_, 1, result, 1);
    cout << result << endl;
}

// 直接递归即可，根据父节点的编号，确定子节点的操作次数

编辑于 2024-03-20 21:34:08 回复(0)

小狮子老黄

/*
使用递归吧，先使用一个二维数组存储整个树。然后每次深度优先遍历整个树。对于每一个节点，
记录这个节点处要增加的次数（注意是不包括其父节点要增加的次数）。
*/

#include <iostream>
#include <vector>
using namespace std;
long long ans = 0;
void BFS(vector<vector<int>>& leftNodes, vector<int>& nodesValue, int node, int target, int last_target) {
    nodesValue[node] = node;
    for(int i = 0; i < leftNodes[node].size(); ++i) {
        int Newnode = leftNodes[node][i];
        int Newtarget = Newnode - (nodesValue[Newnode] + target);
        BFS(leftNodes, nodesValue, Newnode, target + Newtarget, target);
    }
    
ans += (target - last_target);
}

int main() {
    int n;
    cin>>n;
    vector<vector<int>> leftNodes(n+1);
    vector<int> nodesValue(n+1, 1);
    for(int i = 0; i < n-1; ++i) {
        int u, v;
        cin>>u>>v;
        if(u > v) swap(u, v);
        leftNodes[u].emplace_back(v);
    }

    for(int i = 2; i <= n; ++i) {
        int target = i - nodesValue[i];
        if(target == 0) continue;
        BFS(leftNodes, nodesValue, i, target, 0);
    }
    cout << ans;
    return 0;
}   
// 64 位输出请用 printf("%lld")

发表于 2023-09-30 11:39:37 回复(0)

Handa_Rei

没绕过来，暴力递归过了

import sys
sys.setrecursionlimit(100000000)
n = int(input())
mp = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    if u > v:
        u, v = v, u
    mp[u].append(v)


def dfs(i: int, pre: int) -> int:
    ans = i - (pre)
    for nxt in mp[i]:
        ans += dfs(nxt, i)
    return ans
print(dfs(1,1))

发表于 2023-09-01 17:28:16 回复(0)

提交观点

问题信息

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

难度：

4条回答 6收藏 1581浏览

树上节点

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题