ツリーは、エッジの 1 つを削除することによって 2 つの異なるツリーに分割できます。N
範囲内の整数で一意に識別されるノードを持つツリーが与えられた場合、ツリー[0, N-1]
から削除する必要があるエッジを見つける関数を作成する必要があります。結果として得られるツリーのすべてのノード ID の合計の差は次のようになります。最小化。
この関数は、検出した最小の差異を標準出力 (stdout) に出力する必要があります。
この関数は次の引数を受け取ります。
parent
これは次の意味を持つ整数の配列です: parent[i]
= ノードの親i
(より具体的にはその ID)
parent[i] = -1
i に親がない場合 (i はツリーのルート)
データの制約
ツリー内のノードの最大数は 50,000 です
効率の制約
この関数は、2 秒以内に結果を出力することが期待されています
例
Input parent: [1, 4, 4, 2, -1, 2, 2]
aka : 4
/ \
1 2
/ / | \
0 3 5 6
Output: 9
説明: ノード 2 と 6 の間のエッジを削除します。