
ZOJ Problem Set  4112
DreamGrid has just found two trees, both consisting of $n$ vertices, in his right pocket. Each edge in each tree has its own weight. The $i$th edge in the first tree has a weight of $a_i$, while the $i$th edge in the second tree has a pair of weight, denoted by $(b_i, c_i)$. Let ${}^1\!u$ be the $u$th vertex in the first tree, and ${}^2\!u$ be the $u$th vertex in the second tree. Let $\mathbb{E}_1({}^1\!u, {}^1\!v)$ be the set containing the indices of all the edges on the path between the $u$th and the $v$th vertex in the first tree. Similarly, let $\mathbb{E}_2({}^2\!u, {}^2\!v)$ be the set containing the indices of all the edges on the path between the $u$th and the $v$th vertex in the second tree. Define the following values:
As DreamGrid is bored, he decides to count the number of good indices. DreamGrid considers an index $i$ ($1 \le i \le n$) is good, if for all $1 \le j \le n$ and $j \ne i$, $A_{\min}({}^1\!i, {}^1\!j) \ge \min(B_{\max}({}^2\!i, {}^2\!j), C_{\max}({}^2\!i, {}^2\!j))$. Please help DreamGrid figure out all the valid indices. InputThere are multiple test cases. The first line contains an integer $T$, indicating the number of test cases. For each test case: The first line contains an integer $n$ ($2 \le n \le 10^5$), indicating the number of vertices in both trees. For the following $(n1)$ lines, the $i$th line contains three integers ${}^1\!u_i$, ${}^1\!v_i$ and $a_i$ ($1 \le {}^1\!u_i, {}^1\!v_i \le n$, $1 \le a_i \le 10^9$), indicating that there is an edge, whose weight is $a_i$, connecting vertex $u_i$ and $v_i$ in the first tree. For the following $(n1)$ lines,the $i$th line contains four integers ${}^2\!u_i$, ${}^2\!v_i$, $b_i$ and $c_i$ ($1 \le {}^2\!u_i, {}^2\!v_i \le n$, $1 \le b^2_i, c^2_i \le 10^9$), indicating that there is an edge, whose weight is $(b_i, c_i)$, connecting vertex $u_i$ and $v_i$ in the second tree. It's guaranteed that the sum of $n$ of all test cases does not exceed $1.5 \times 10^5$. OutputFor each test case output $k$ integers ($k$ is the number of valid indices) in one line separated by a space in increasing order, indicating the indices of the valid vertices. Note that if there is no valid vertex, you should print "1" instead. Sample Input2 2 1 2 1 1 2 2 3 4 1 2 7 1 3 8 1 4 12 1 2 8 8 2 3 9 7 2 4 6 4 Sample Output1 3 4 Author: JIANG, Shibiao Source: The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple 