题目描述
给定一颗根为1号节点的数,每个节点初始权值为1.现在每次可以选择一个节点,使其子树所有节点的权值加1,最少多少次操作可以使得每个节点的权值等于其编号。
输入描述:
第一行 :树上节点数量 - 2≤n≤100000;
接下来n-1行:u号节点和v号节点间有一条边相连 - 1≤u,v≤n
输出描述:
最小操作次数
样例
3
1 2
1 3
3
(DFS) $O(n^2)$
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n;
int h[N], e[N * 2], ne[N * 2], idx;
bool st[N];
long ans;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void DFS(int root, int parent) {
st[root] = true;
ans += root - parent;
for (int i = h[root]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
DFS(j, root);
}
}
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
DFS(1, 1);
cout << ans;
}