[POI2018]Plan metra
题目描述
有一棵 $n$ 个点的无根树,每条边有一个正整数权值,表示长度,定义两点距离为在树上的最短路径的长度。
已知 $2$ 到 $ n-1$ 每个点在树上与 $1$ 和 $n$ 的距离,请根据这些信息还原出这棵树。
输入输出格式
输入格式
第一行包含一个正整数 $n$,表示点数。
第二行包含 $n-2$ 个正整数 $d(1,2),d(1,3),...,d(1,n-1)$,分别表示每个点到 $1$ 的距离。
第三行包含 $n-2$ 个正整数 $d(n,2),d(n,3),...,d(n,n-1)$,分别表示每个点到 $n$ 的距离。
输出格式
若无解,输出 `NIE`。
否则第一行输出`TAK`,接下来 $n-1$ 行每行三个正整数 $u,v,c$,表示存在一条长度为 $c$ 的连接 $u$ 和 $v$ 两点的树边。
若有多组解,输出任意一组即可。
**本题使用 Special Judge。**
输入输出样例
输入样例 #1
7
6 6 2 2 1
5 3 5 1 4
输出样例 #1
TAK
1 5 2
5 7 1
5 2 4
7 3 3
1 4 2
1 6 1
说明
对于 $100\%$ 的数据,$2\le n\le 500000$,$1\le d\le 1000000$,$1\le u,v\le n$,$1\le c\le1000000$。