Vương quốc JOI có $N$ thành phố, được đánh số từ $1$ đến $N$. Thành phố $1$ là thủ đô. Mỗi thành phố có một giá trị gọi là độ sôi động, và độ sôi động ban đầu của thành phố $i$ ($1 \le i \le N$) là $C_i$.
Một con đường trong Vương quốc JOI nối hai thành phố khác nhau theo cả hai chiều. Ban đầu, Vương quốc JOI không có con đường nào. Bạn đã lên kế hoạch xây dựng $N-1$ con đường. Lần xây dựng thứ $j$ ($1 \le j \le N-1$) được dự định thực hiện như sau.
- Hai thành phố $A_j$ và $B_j$ được chỉ định, sao cho chỉ sử dụng những con đường đã xây dựng đến thời điểm đó, ta có thể đi từ thành phố $1$ đến thành phố $A_j$ nhưng không thể đi từ thành phố $1$ đến thành phố $B_j$.
- Bạn xây dựng một con đường nối thành phố $A_j$ và thành phố $B_j$. Chi phí xây dựng là số cặp thành phố $(s,t)$ thỏa mãn các điều kiện sau:
Thành phố $s$ và thành phố $t$ nằm trên đường đi ngắn nhất từ thành phố $1$ đến thành phố $A_j$; khi đi từ thành phố $1$ đến thành phố $A_j$, ta đến thành phố $s$ trước thành phố $t$; và độ sôi động của thành phố $s$ lớn hơn nghiêm ngặt độ sôi động của thành phố $t$.
Ở đây, các thành phố nằm trên đường đi từ thành phố $1$ đến thành phố $A_j$ bao gồm cả thành phố $1$ và thành phố $A_j$. Lưu ý rằng đường đi ngắn nhất từ thành phố $1$ đến thành phố $A_j$ là duy nhất.
- Độ sôi động của tất cả các thành phố nằm trên đường đi từ thành phố $1$ đến thành phố $A_j$ được đổi thành độ sôi động của thành phố $B_j$.
Bạn muốn biết chi phí của mỗi lần xây dựng.
Yêu cầu
Cho dữ liệu về các thành phố và các lần xây dựng đường, hãy viết chương trình tính chi phí của mỗi lần xây dựng.
Dữ liệu vào
Đọc dữ liệu sau từ đầu vào chuẩn.
- Dòng đầu tiên chứa một số nguyên $N$. Điều này có nghĩa là Vương quốc JOI có $N$ thành phố.
- Dòng thứ hai chứa $N$ số nguyên $C_1,C_2,\ldots,C_N$, cách nhau bởi dấu cách. Điều này có nghĩa là độ sôi động ban đầu của thành phố $i$ ($1 \le i \le N$) là $C_i$.
- Dòng thứ $j$ ($1 \le j \le N-1$) trong $N-1$ dòng tiếp theo chứa hai số nguyên $A_j,B_j$, cách nhau bởi dấu cách. Điều này có nghĩa là thành phố $A_j$ và thành phố $B_j$ được chỉ định cho lần xây dựng đường thứ $j$.
Dữ liệu ra
Ghi $N-1$ dòng ra đầu ra chuẩn. Dòng thứ $j$ ($1 \le j \le N-1$) chứa chi phí của lần xây dựng đường thứ $j$.
Giới hạn
Tất cả dữ liệu vào thỏa mãn các điều kiện sau.
- $1 \le N \le 100\,000$.
- $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
- $1 \le A_j \le N$ ($1 \le j \le N-1$).
- $1 \le B_j \le N$ ($1 \le j \le N-1$).
- Chỉ sử dụng những con đường được xây dựng trước lần xây dựng thứ $j$, ta có thể đi từ thành phố $1$ đến thành phố $A_j$ nhưng không thể đi từ thành phố $1$ đến thành phố $B_j$ ($1 \le j \le N-1$).
Nhiệm vụ con
Có 3 nhiệm vụ con. Điểm số và giới hạn bổ sung của mỗi nhiệm vụ con như sau:
Nhiệm vụ con 1 [7 điểm]
- $N \le 500$.
Nhiệm vụ con 2 [9 điểm]
- $N \le 4000$.
Nhiệm vụ con 3 [84 điểm]
Không có giới hạn bổ sung.
Ví dụ
Dữ liệu vào 1
5 1 2 3 4 5 1 2 2 3 2 4 3 5
Dữ liệu ra 1
0 0 0 2
Ghi chú
Trong dữ liệu vào mẫu 1, các lần xây dựng được thực hiện như sau:
- Ở lần xây dựng thứ nhất, không có cặp $(s,t)$ nào thỏa mãn các điều kiện, nên chi phí là $0$. Một con đường nối thành phố $1$ và thành phố $2$ được xây dựng, và độ sôi động của thành phố $1$ đổi thành $2$.
- Ở lần xây dựng thứ hai, cũng không có cặp $(s,t)$ nào thỏa mãn các điều kiện, nên chi phí là $0$. Một con đường nối thành phố $2$ và thành phố $3$ được xây dựng, và độ sôi động của thành phố $1$ và thành phố $2$ đổi thành $3$.
- Ở lần xây dựng thứ ba, cũng không có cặp $(s,t)$ nào thỏa mãn các điều kiện, nên chi phí là $0$. Một con đường nối thành phố $2$ và thành phố $4$ được xây dựng, và độ sôi động của thành phố $1$ và thành phố $2$ đổi thành $4$.
- Ở lần xây dựng thứ tư, hai cặp $(s,t)=(1,3),(2,3)$ thỏa mãn các điều kiện, nên chi phí là $2$. Một con đường nối thành phố $3$ và thành phố $5$ được xây dựng, và độ sôi động của thành phố $1$, thành phố $2$ và thành phố $3$ đổi thành $5$.
Dữ liệu vào 2
10 1 7 3 4 8 6 2 9 10 5 1 2 1 3 2 4 3 5 2 6 3 7 4 8 5 9 6 10
Dữ liệu ra 2
0 0 0 1 1 0 1 2 3