D-Balanced Tree
Time limit2sMemory limit512 MB
Given a tree with each vertex colored black or white, find the smallest D such that every vertex has another vertex of the same color within distance D, or -1 if impossible.
- Level
Hard8 of 10
- Topics
- Tree, DFS, Binary search, Greedy
- Solved
- No attempts yet
Problem
A D-balanced tree is a tree that satisfies the following three conditions.
- Every vertex of the tree is either black or white.
- For every black vertex, there exists another black vertex at distance at most D from it.
- For every white vertex, there exists another white vertex at distance at most D from it.
Given a tree and the colors of its vertices, find the minimum value of D that satisfies the conditions.
Input
The first line gives the number of test cases T. Each test case is structured as follows.
- The first line gives the number of vertices N.
- The next N-1 lines each give two integers x and y. They denote the edge connecting vertices x and y.
- The last line gives the colors of vertices 1 through N in order. 0 means white and 1 means black.
Output
For each test case, print the minimum value of D that satisfies the conditions, one per line. If no valid value of D exists, print -1.
Constraints
- 3 ≤ N ≤ 500,000
- The sum of N is at most 500,000.
- The distance between two vertices A and B equals the number of distinct edges on the path that starts at A and ends at B.