john9's blog

Problem on Tree
By john9, 12 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
}
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks for the solution but can memoization be used here

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's unnecessary. There will be only one call of dfs for each vertex because it is a tree.

      → Reply