{"problem":{"name":"Cleaning","description":{"content":"There is a tree with $N$ vertices, numbered $1$ through $N$. The $i$\\-th of the $N-1$ edges connects vertices $a_i$ and $b_i$. Currently, there are $A_i$ stones placed on vertex $i$. Determine whether","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc010_c"},"statements":[{"statement_type":"Markdown","content":"There is a tree with $N$ vertices, numbered $1$ through $N$. The $i$\\-th of the $N-1$ edges connects vertices $a_i$ and $b_i$.\nCurrently, there are $A_i$ stones placed on vertex $i$. Determine whether it is possible to remove all the stones from the vertices by repeatedly performing the following operation:\n\n*   Select a pair of different leaves. Then, remove exactly one stone from every vertex on the path between those two vertices. Here, a _leaf_ is a vertex of the tree whose degree is $1$, and the selected leaves themselves are also considered as vertices on the path connecting them.\n\nNote that the operation cannot be performed if there is a vertex with no stone on the path.\n\n## Constraints\n\n*   $2 ≦ N ≦ 10^5$\n*   $1 ≦ a_i,b_i ≦ N$\n*   $0 ≦ A_i ≦ 10^9$\n*   The given graph is a tree.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ … $A_N$\n$a_1$ $b_1$\n:\n$a_{N-1}$ $b_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc010_c","tags":[],"sample_group":[["5\n1 2 1 1 2\n2 4\n5 2\n3 2\n1 3","YES\n\nAll the stones can be removed, as follows:\n\n*   Select vertices $4$ and $5$. Then, there is one stone remaining on each vertex except $4$.\n*   Select vertices $1$ and $5$. Then, there is no stone on any vertex."],["3\n1 2 1\n1 2\n2 3","NO"],["6\n3 2 2 2 2 2\n1 2\n2 3\n1 4\n1 5\n4 6","YES"]],"created_at":"2026-03-03 11:01:13"}}