问题 B: Simple Tree Problem

There is an undirected tree with $n$ vertices and $n-1$ edges.

The i-th vertex has a positive integer value of ai($i=1,2,\dots ,n$).

The $i$-th edge has a positive integer value of ki($i=1,2,\dots ,n-1$).

We define$f(x,T)$ as the total number of vertices in tree $T$ with value equal to $x$.

We define $g(y,T)$ as the maximum $x$ that satisfies $f(x,T)$ is not less than $y$, if there is no $x$ that satisfies the condition, then $g(y,T)$ is equal to $0$.

For the $i$-th edge, if we remove it, the original tree will be divided into two new trees, denoted as $Ti1$ and $Ti2$, respectively.

For the $i$-th edge, you need to calculate max,max(g(ki,Ti1),g(ki,Ti2))($i=1,2,\dots ,n-1$).

$\text{Please note that for each edge, we will not really remove it.}$

$\text{Please pay attention to the time complexity of your program.}$

Each test contains multiple test cases. The first line of input contains a single integer $t(1\le t\le 10^6)$——the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n(1\le n\le 10^6)$ —— the number of vertices.

The second line of each test case contains $n$ integers ai(1≤ai≤10^9) —— indicating the value of each vertex.

The following $n-1$ lines of each test case contains three integers ui,vi and ki (1≤ui,vi,ki≤n,ui=vi) —— indicating an edge with value ki between vertices ui and vi. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ does not exceed 3×10^6.

For each testcase, output $n-1$ lines, where the $i$-th line contains an integer representing the answer to the $i$-th edge.

Notes: In this problem,

you may need more stack space to pass this problem. We suggest you to add the following code into your main function if you use C++.

int main() {
int size(512<<20); // 512M
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
// YOUR CODE
...
exit(0);
}

And if you use the code above please $\text{DON’T forget to add exit(0)}$; in the end of your main function, otherwise your code may get RE.

3
5
5 2 1 2 2
3 4 2
3 2 1
2 1 1
2 5 1
5
2 1 3 1 5
2 4 1
2 1 2
1 3 2
1 5 3
1
3

2
5
5
5
5
1
1
0