给你一棵树，完全被海狸占据。树是一个没有圈的连通无向图。树由n个顶点组成，第i个顶点包含ki个海狸。
“Beavermoncher-0xFF”的工作原理如下：在某个顶点u，如果它们通过一条边连接，它可以到达顶点v，并正好吃掉位于顶点v的一只海狸。如果v中没有海狸，则不可能移动到顶点v。
为什么“Beavermoncher-0xFF”会这样工作？因为开发商没有为电池提供位置，吃海狸是将其质量转化为纯能量的必要条件。
可以保证海狸会被正在发生的事情震惊，这就是为什么它们不能从树的一个顶点移动到另一个顶点的原因。
至于“Beavermoncher-0xFF”，在满足上述条件的情况下，它可以沿每条边向两个方向移动。
树的根位于顶点s。这意味着“Beavermoncher-0xFF”在顶点s开始它的任务，它必须在实验结束时返回那里，因为没有人会将它从高处取下。
确定海狸“Beavermoncher-0xFF”可以进食并返回起始顶点的最大数量。
"Eat a beaver, save a tree!" − That will be the motto of ecologists' urgent meeting in Beaverley Hills.
And the whole point is that the population of beavers on the Earth has reached incredible sizes! Each day their number increases in several times and they don't even realize how much their unhealthy obsession with trees harms the nature and the humankind. The amount of oxygen in the atmosphere has dropped to 17 per cent and, as the best minds of the world think, that is not the end.
In the middle of the 50-s of the previous century a group of soviet scientists succeed in foreseeing the situation with beavers and worked out a secret technology to clean territory. The technology bears a mysterious title "Beavermuncher-0xFF". Now the fate of the planet lies on the fragile shoulders of a small group of people who has dedicated their lives to science.
The prototype is ready, you now need to urgently carry out its experiments in practice.
You are given a tree, completely occupied by beavers. A tree is a connected undirected graph without cycles. The tree consists of
n vertices, the
i-th vertex contains
ki beavers.
"Beavermuncher-0xFF" works by the following principle: being at some vertex
u, it can go to the vertex
v, if they are connected by an edge, and eat
exactly one beaver located at the vertex
v. It is impossible to move to the vertex
v if there are no beavers left in
v. "Beavermuncher-0xFF"
cannot just stand at some vertex and eat beavers in it. "Beavermuncher-0xFF" must move without stops.
Why does the "Beavermuncher-0xFF" works like this? Because the developers have not provided place for the battery in it and eating beavers is necessary for converting their mass into pure energy.
It is guaranteed that the beavers will be shocked by what is happening, which is why they will not be able to move from a vertex of the tree to another one. As for the "Beavermuncher-0xFF", it can move along each edge in both directions while conditions described above are fulfilled.
The root of the tree is located at the vertex
s. This means that the "Beavermuncher-0xFF" begins its mission at the vertex
s and it must return there at the end of experiment, because no one is going to take it down from a high place.
Determine the maximum number of beavers "Beavermuncher-0xFF" can eat and return to the starting vertex.
Output
Print the maximum number of beavers munched by the "Beavermuncher-0xFF".
Please, do not use
%lld specificator to write 64-bit integers in C++. It is preferred to use
cout (also you may use
%I64d).