题目大意：

　　一棵$n(n\le5\times10^5)$个结点的树，每条边的边权均为正整数，告诉你$2\sim n-1$号结点到$1$号点和$n$号点的距离$d1[i]$和$d2[i]$。求是否存在这样的树，若存在，则构造出这样一棵树。

思路：

　　若对于所有的$1<i<n$，$|d1[i]-d2[i]|$都相等，则$1$与$n$直接相连，其余点与$1$和$n$中最近的点相连。

　　否则若存在这样的树，肯定能构造出一种方案，使得$d1[n]=\min\{d1[i]+d2[i]\}$。令$d=\min\{d1[i]+d2[i]\}$，若点$i$满足$d1[i]+d2[i]=d$，则$i$一定在$1$到$n$的链上。通过排序可以求出$1$到$n$的链，如果发现有两点在同一位置，则构造失败。对于剩下的点$i$，向满足$d1[j]=d-\frac{d1[i]-d2[i]+d}2$的点$j$连一条长度为$d1[i]-d1[j]$的边即可，如果不存在这样的点$j$，则构造失败，若新建边长度不为正整数则还是构造失败。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 class MMapInput { 7     private: 8         char *buf,*p; 9         int size;10     public:11         MMapInput() {12             register int fd=fileno(stdin);13             struct stat sb;14             fstat(fd,&sb);15             size=sb.st_size;16             buf=reinterpret_cast
          
           (mmap(0,size,PROT_READ,MAP_PRIVATE,fileno(stdin),0));17 p=buf;18 }19 char getchar() {20 return (p==buf+size||*p==EOF)?EOF:*p++;21 }22 };23 MMapInput mmi;24 inline int getint() {25 register char ch;26 while(!isdigit(ch=mmi.getchar()));27 register int x=ch^'0';28 while(isdigit(ch=mmi.getchar())) x=(((x<<2)+x)<<1)+(ch^'0');29 return x;30 }31 const int N=5e5+1,C=1e6;32 int d1[N],d2[N],cnt,tmp[N],mem[C<<1],*vis=mem+C;33 struct Edge {34 int u,v,w;35 };36 Edge e[N];37 inline bool cmp(const int &a,const int &b) {38 return d1[a]
           
            d2[i]?n:1,std::min(d1[i],d2[i])};55 }56 } else case2: {57 int d=C*2;58 for(register int i=2;i