ルートからのパスの合計
あなたには
n 個のノードを持つ木が与えられています。i 番目のノードには () という値が割り当てられています。ここで、目的はその木の根ノードから始まるパスのうち、合計値が与えられた s と等しいものの数を求めることです。入力
最初の行には、スペースで区切られた 2 つの整数
n と s () が与えられます。これは、それぞれ木のノード数と求めたい合計値を表します。
2 行目には、 から () までの値がスペース区切りで与えられ、各ノードに割り当てられた値を示します。
続く n-1 行では、各行にノード a と b (1 ≤ a, b ≤ n) がスペース区切りで書かれており、ノード a とノード b に辺があることを示します。これらの辺が正しく木を形成していることは保証されています。出力
根ノードから始まるパスのうち、合計が
s と等しいものの数を表す整数を 1 つ出力してください。Examples
入力 | 出力 |
5 6
1 2 3 4 5
1 2
2 3
1 5
5 4 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB