Tìm nút có hiệu tuyệt đối với X nhỏ nhất trong cây trong C++

Cho cây, trọng số các nút và số nguyên x. Tìm nút i sao cho |weight[i] - x| là nhỏ nhất (title nói maximum nhưng code tìm minimum). Ví dụ: x=15, trọng số: 1→5, 2→10, 3→11, 4→8, 5→6. Kết quả nút 3 (|11-15|=4).

Duyệt DFS toàn cây, cập nhật nút cho hiệu tuyệt đối nhỏ nhất.

Ví dụ

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

int min_value = INT_MAX, x, result;
vector<int> graph[100];
vector<int> weight(100);

void dfs(int node, int parent) {
    if (min_value > abs(weight[node] - x)) {
        min_value = abs(weight[node] - x);
        result = node;
    }
    for (int to : graph[node]) {
        if (to == parent) continue;
        dfs(to, node);
    }
}

int main() {
    x = 15;
    weight[1] = 5; weight[2] = 10; weight[3] = 11; weight[4] = 8; weight[5] = 6;
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[2].push_back(4);
    graph[1].push_back(5);
    dfs(1, 1);
    cout << "The node number is: " << result;
}

Kết quả

The node number is: 3