これは、ある企業で尋ねられたコーディングの問題でした。
N 個のノードと、各ノードとエッジに関連付けられた重みを持つツリーが与えられます (ツリーに存在します)。作成された 2 つのツリーの重みの合計の差が最大になるように、1 つのエッジを削除する必要があります。
入力：
最初の行には N が含まれています。ノードの 2 番目の行には、各ノードの重みを示す N 個の積分が含まれ、その後に存在するエッジを示す N-1 行が続きます。
出力：
作成されたツリーの重みの最大差。
例：
入力：
最初のテスト ケース:
3
8 7 8
10
21
出力：7
2 番目のテスト ケース:
9
5 5 4 1 8 8 3 5 2
10
20
31
41
53
60
75
81
出力: 13(この出力については不明)