AT_arc108_f [ARC108F] Paint Tree

[problemUrl]: https://atcoder.jp/contests/arc108/tasks/arc108_f $ 1 $ から $ N $ の番号がついた $ N $ 個の頂点と、$ 1 $ から $ N-1 $ の番号がついた $ N-1 $ 本の辺からなる木が与えられます。 辺 $ i $ は頂点 $ a_i $ と頂点 $ b_i $ を双方向につなぐ長さ $ 1 $ の辺です。 すぬけ君はそれぞれの頂点を白か黒のどちらかで塗ります。 塗り方の *良さ* は、白色の頂点同士の距離の最大値を $ X $、黒色の頂点同士の距離の最大値を $ Y $ として $ \max(X,Y) $ です。 ここで、その色の頂点が存在しない場合の距離の最大値は $ 0 $ とすることにします。 頂点への色の塗り方は $ 2^N $ 通りあります。それぞれの塗り方について良さを計算し、その総和を $ 10^{9}+7 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_{N-1} $ $ b_{N-1} $

それぞれの塗り方について良さを計算し、その総和を $ 10^{9}+7 $ で割ったあまりを出力せよ。

### 制約 - 与えられる入力は全て整数 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^{5} $ - $ 1\ \leq\ a_i,\ b_i\ \leq\ N $ - 与えられるグラフは木 ### Sample Explanation 1 \- 頂点 $ 1,2 $ の両方を同じ色で塗ったときの良さは $ 1 $ で、異なる色で塗ったときの良さは $ 0 $ です。 - 塗り方の良さの総和は $ 2 $ となります。 ### Sample Explanation 3 \- $ 10^{9}+7 $ で割ったあまりを求めるのを忘れずに。