1、找到d1[i]+dn[i] 最小的点，作为1到n链上的点

2、令链长为D，若abs（d1[i]-dn[i]）==D，则 i 与1或n 连边

3、对于链上除去1和n的点k，若 dn[i]-d1[i]==dn[k]-d1[k]，则i与k连边

若1到n的链上没有点，即1与n直接相连，那么所有的d1[i]-dn[i] 相等 且 不为 0

特判n=2，输出1 2 任意长度[1,1e6]

无解的情况：

1、找出的链上的点，存在两个点i，j，d1[i]==d1[j]

2、对于某个点i，找不到对应的点k

 

#include
     
      #include
      
       #include
       
        using namespace std;#define N 500001#define M 1000001int dis1[N],disn[N];int cnt[M<<1];int chain[N];bool vis[N];struct node1{    int id,d,bl;}e[N];struct node2{    int id,d;}g[N];void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}bool cmp(int p,int q){    return dis1[p]
        
         disn[i]) printf("%d %d %d\n",n,i,dis1[i]-sta);            else printf("1 %d %d\n",i,disn[i]-sta);        return 0;    }    int mid=0;    dis1[0]=1e7;    for(int i=2;i
         
          m)        {            puts("NIE");            return 0;        }        if(e[i].d
          
           g[now].d) now++; i--; } }// return 0; puts("TAK"); printf("1 %d %d\n",chain[1],dis1[chain[1]]); for(int i=2;i<=m;++i) printf("%d %d %d\n",chain[i-1],chain[i],dis1[chain[i]]-dis1[chain[i-1]]); printf("%d %d %d\n",chain[m],n,disn[chain[m]]); for(int i=2;i
          
         
        
       
      
     

 

5100: [POI2018]Plan metra

Time Limit: 40 Sec  Memory Limit: 128 MBSec  Special Judge

Submit: 277  Solved: 69

[][][]

Description

有一棵n个点的无根树，每条边有一个正整数权值，表示长度，定义两点距离为在树上的最短路径的长度。

已知2到n-1每个点在树上与1和n的距离，请根据这些信息还原出这棵树。

 

 

Input

第一行包含一个正整数n(2<=n<=500000)，表示点数。

第二行包含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的距离。

输入数据保证1<=d<=1000000。

 

 

Output

若无解，输出NIE。

否则第一行输出TAK，接下来n-1行每行三个正整数u,v,c(1<=u,v<=n,1<=c<=1000000)

表示存在一条长度为c的连接u和v两点的树边。

若有多组解，输出任意一组。

 

 

Sample Input

7

6 6 2 2 1

5 3 5 1 4

Sample Output

TAK

1 5 2

5 7 1

5 2 4

7 3 3

1 4 2

1 6 1