P5959 [POI 2018] Metro Plan

There is an unrooted tree with $n$ nodes. Each edge has a positive integer weight representing its length. The distance between two nodes is defined as the length of the shortest path between them in the tree. You are given, for every node from $2$ to $n-1$, its distance to node $1$ and its distance to node $n$ in the tree. Reconstruct the tree from this information.

The first line contains a positive integer $n$, representing the number of nodes. The second line contains $n-2$ positive integers $d(1,2),d(1,3),...,d(1,n-1)$, representing the distance from each node to node $1$. The third line contains $n-2$ positive integers $d(n,2),d(n,3),...,d(n,n-1)$, representing the distance from each node to node $n$.

If there is no solution, output `NIE`. Otherwise, output `TAK` on the first line. Then output $n-1$ lines, each containing three positive integers $u,v,c$, indicating that there is a tree edge connecting nodes $u$ and $v$ with length $c$. If there are multiple solutions, output any one of them. **This problem uses a Special Judge.**

For $100\%$ of the testdata, $2\le n\le 500000$, $1\le d\le 1000000$, $1\le u,v\le n$, $1\le c\le1000000$. Translated by ChatGPT 5