12055


表題の件について質問です。  
HackerRankというサイトでプログラミングの問題を解いています。  
データ構造は以下のコードで作りその後ノードの値を足しあわせていこうと思ったのですが、  
どのように合計値を計算すればよいのか方針が分かりません。  
ヒントやアドバイスをいただけないでしょうか。  
※もし、データ構造に問題がありましたらそれも合わせてご教示いただけると幸いです。

よろしくお願いします。

[問題]  
<https://www.hackerrank.com/challenges/cut-the-tree>

[コード]

[code]

    class Tree:
        """
        Original Tree Structure which is representing the Input
        """
        def __init__(self, value, position):
            """
            Initialize class instance
            :param value: value of the node
            """
            self.value = value
            self.position = position
            self.connection = []
    
        def set_connection(self, connection):
            """
            set connection with other instance
            :param connection:
            """
            self.connection.append(connection)
    
        def set_value(self, value):
            """
            set value of the instance
            :param value: value
            """
            self.connection = value
    
        def get_value(self, position):
            return self.value
    
        def get_sum(self):
            """
            Running Tree and sum up the value of node.
            :param frm: which node coming from
            :param to: which node goes next
            :return: sum value
            """
            return self.value
    
        def get_position(self):
            return self
    
    if __name__ == "__main__":
    
        # ----- Initializing ------
        N = int(input())
        values = input().split()
        T = []
        a = 0
        for value in values:
            T.append(Tree(int(value), a))
            a += 1
    
        input_list = []
        for i in range(N-1):
            in_con = input().split()
            T[int(in_con[0])-1].set_connection(int(in_con[1])-1)
            T[int(in_con[1])-1].set_connection(int(in_con[0])-1)
            input_list.append(in_con)
    
        # ----- Start searching -----
    
        〜ここから値の走査を始める〜
    
[/code]


CC BY-SA 3.0
2015-07-05T13:04:48.480
12051
2015-07-05T15:55:58.173
2015-07-05T15:55:58.173
5363
7738
question
python binary-tree
Tree 構造の走査及び値の算出


リンク先の問題文をよく読んでみると、どの vertex がルートになるかの指定がありませんし、一つの vertex から出ていく edge
の数が高々２本であるという制約もありません。したがってバイナリツリーで表現するのは得策ではありません。

むしろ (ループのない) 無向グラフとして表した方がよいと思います。深さ優先探索 (depth first search)
というアルゴリズムを使って、edge の一方の側の合計を求めていきます。全体の合計は簡単に求められるので、片方の合計が分かれば、Tree_diff
も簡単に求められます。  
この方法なら、どの vertex から始めても大丈夫なはずです。


CC BY-SA 3.0
2015-07-05T15:15:58.837
12055
2015-07-05T15:15:58.837
3605
12051
answer