题目描述

Note the** unusual memory limit **for this problem. Given a rooted tree with $n$ nodes and $n-1$ edges. The $i$-th edge can be described by $(a_i, b_i)$, which represents an edge connecting node $a_i$ and node $b_i$, where node $a_i$ is the parent of node $b_i$. There are $n-1$ queries. The $i$-th query contains an integer $c_i$, asking for the length of the longest simple path starting from node $c_i$ in the graph (forest) formed by the first $i$ edges. It is guaranteed that there does not exist $j$ such that $1 \leq j \leq i$ and $b_j = c_i$, i.e., $c_i$ is the root of a tree in the forest.官方中文

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^5$). The description of the test cases follows. The first line of each test case contains an integer $n$ ($2 \leq n \leq 10^6$), representing the number of nodes in the tree. The next $n-1$ lines each contain three integers $a_i, b_i, c_i$ ($1 \leq a_i, b_i, c_i \leq n, a_i \neq b_i$), representing that the parent of node $b_i$ is $a_i$, and the $i$-th query is $c_i$. It is guaranteed that:For each test case, the $n-1$ edges form a rooted tree.For each test case, for any $1 \leq i \leq n-1$, there does not exist $j$ such that $1 \leq j \leq i$ and $b_j = c_i$.The sum of $n$ over all test cases does not exceed $10^6$.官方中文

输出格式

For each test case, output $n-1$ integers in one line. The $i$-th integer represents your answer to the $i$-th query.官方中文