{"problem":{"name":"Black Radius","description":{"content":"There is a tree with $N$ vertices. The vertices are numbered $1$ through $N$. For each $1 ≤ i ≤ N - 1$, the $i$\\-th edge connects vertices $a_i$ and $b_i$. The lengths of all the edges are $1$. Snuke ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc008_f"},"statements":[{"statement_type":"Markdown","content":"There is a tree with $N$ vertices. The vertices are numbered $1$ through $N$. For each $1 ≤ i ≤ N - 1$, the $i$\\-th edge connects vertices $a_i$ and $b_i$. The lengths of all the edges are $1$.\nSnuke likes some of the vertices. The information on his favorite vertices are given to you as a string $s$ of length $N$. For each $1 ≤ i ≤ N$, $s_i$ is `1` if Snuke likes vertex $i$, and `0` if he does not like vertex $i$.\nInitially, all the vertices are white. Snuke will perform the following operation exactly once:\n\n*   Select a vertex $v$ that he likes, and a non-negative integer $d$. Then, paint all the vertices black whose distances from $v$ are at most $d$.\n\nFind the number of the possible combinations of colors of the vertices after the operation.\n\n## Constraints\n\n*   $2 ≤ N ≤ 2×10^5$\n*   $1 ≤ a_i, b_i ≤ N$\n*   The given graph is a tree.\n*   $|s| = N$\n*   $s$ consists of `0` and `1`.\n*   $s$ contains at least one occurrence of `1`.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$a_2$ $b_2$\n$:$\n$a_{N - 1}$ $b_{N - 1}$\n$s$\n\n## Partial Score\n\n*   In the test set worth $1300$ points, $s$ consists only of `1`.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc008_f","tags":[],"sample_group":[["4\n1 2\n1 3\n1 4\n1100","4\n\nThe following four combinations of colors of the vertices are possible:\n\n![image](https://atcoder.jp/img/agc008/334d566ec1f4f38d23cd580044f1cd07.png)"],["5\n1 2\n1 3\n1 4\n4 5\n11111","11\n\nThis case satisfies the additional constraint for the partial score."],["6\n1 2\n1 3\n1 4\n2 5\n2 6\n100011","8"]],"created_at":"2026-03-03 11:01:14"}}