树上节点

#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;
}

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

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

#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")

没绕过来，暴力递归过了

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))