Блог пользователя john9

Problem on Tree
Автор john9, 12 лет назад, По-английски

A tree can be split into two different trees by removing one of its edges. Given a tree with N nodes uniquely identified by integer numbers in the [0, N-1] range

Your task is to

write a function that finds the edge that needs to be removed from the tree, such that the difference between the sums of all the node IDs in the resulting trees is minimum

your function will print the minimum difference that you found to the standard output (stdout)

Note that your function will receive the following arguments:

parent which is an array of integer numbers with the following meaning: parent[i] = the parent of node i (more specifically its ID)

parent[i] = -1 if i has no parent (i is the root of the tree)

Data constraints

the maximum number of nodes in the tree is 50,000

Efficiency constraints

your function is expected to print the result in less than 2 seconds

Example

Input parent: 1, 4, 4, 2, -1, 2, 2

Output 9

Explanation We remove the edge between nodes 2 and 6.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This is the best I could come up with. I've made a child list using the parent array. The key idea is to find sum of each sub-tree and check whether it is the desired sub-tree or not.

const int MAX_N = int (5e4) + 7;

int total, minDif, root;
vector <int> childList [MAX_N];

int dfs (int u) {
    int sum = u;
    for (int i = 0; i < (int) childList [u].size (); ++i) sum += dfs (childList [u][i]);
    minDif = min (minDif, abs (sum - (total - sum)));
    return sum;
}

int solve (int n, int par []) {
    total = (n * (n - 1)) / 2;
    minDif = INT_MAX;

    for (int i = 0; i < n; ++i) if (par [i] == -1) {
        root = i;
    } else {
        childList [par [i]].push_back (i);
    }
    dfs (root);
    return minDif;
}
→ Ответить