【bzoj5100】[POI2018]Plan metra 构造

题目描述

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

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

输入

第一行包含一个正整数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。

输出

若无解，输出NIE。

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

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

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

样例输入

7
6 6 2 2 1
5 3 5 1 4

样例输出

TAK
1 5 2
5 7 1
5 2 4
7 3 3
1 4 2
1 6 1

题解

构造

考虑两种情况：

(1) $1$ 号点与 $n$ 号点直接相连

此时需要满足：对于所有的 $i$ ，$|d(1,i)-d(n,i)|$ 均相等。

满足此条件时容易构造出解： $1$ 号点与 $n$ 号点的边长度为 $|d(1,i)-d(n,i)|$ ；对于第 $i$ 个点，如果 $d(1,i)<d(n,i)$ 则与 $1$ 相连，长度为 $d(1,i)$ ；否则与 $n$ 相连，长度为 $d(n,i)$ 。

(2) $1$ 号点与 $n$ 号点不直接相连

此时 $1$ 号点与 $n$ 号点的距离为 $min{dis(1,i)+dis(n,i)}$ 。

设这个距离为 $d$ ，那么对于所有的 $dis(1,i)+dis(n,i)=d$ 的点 $i$（包括 $1$ 号点和 $n$ 号点），将其按照 $dis(1,i)$ 从小到大排序，则它们形成了一条从 $1$ 到 $n$ 的链。此时需要满足：这条链上的任意两个点的位置（即 $dis(1,i)$ ）均不同。

然后考虑其它点：对于点 $x$ ，它到 $1$ 号点的方式一定是：先到达链上的某个点，然后再沿着链到 $1$ 。到 $n$ 同理。于是可以算出其到链上某个点的距离 $frac {dis(1,x)+dis(n,x)-d}2$ ，进而得到 $1$ 到这个链上点的距离。此时需要满足： $dis(1,x)+dis(n,x)-d$ 为偶数，且 $|dis(1,x)-dis(n,x)|le d$ ，且存在某个链上的点与 $1$ 的距离为 $dis(1,x)-frac {dis(1,x)+dis(n,x)-d}2$ 。

满足这些条件时容易构造出解： $1$ 号点与 $n$ 号点的链之间的相邻两点 $a$ 和 $b$（$a$ 比 $b$ 更靠近 $1$）连边，长度为 $dis(1,b)-dis(1,a)$ ，其余点向着链上对应的点连边，长度为 $frac{dis(1,x)+dis(n,x)-d}2$ 。

查找对应点时可以使用二分查找解决。

这两种情况均不满足时无解。

时间复杂度 $O(nlog n)$

#include <cstdio>
#include <cctype>
#include <algorithm>
#define N 500010
using namespace std;
struct data
{
    int d , p;
    data() {}
    data(int D , int P) {d = D , p = P;}
    bool operator<(const data &a)const {return d < a.d;}
}v[N];
int a[N] , b[N] , l[N] , tot , x[N] , y[N] , z[N] , cnt;
int main()
{
    int n , i , t , len = 1 << 30 , val;
    scanf("%d" , &n);
    if(n == 2)
    {
        puts("TAK
1 2 1");
        return 0;
    }
    for(i = 2 ; i < n ; i ++ ) scanf("%d" , &a[i]);
    for(i = 2 ; i < n ; i ++ ) scanf("%d" , &b[i]) , l[i] = a[i] + b[i] , len = min(len , l[i]);
    if(a[2] != b[2])
    {
        val = max(a[2] - b[2] , b[2] - a[2]);
        for(i = 3 ; i < n ; i ++ )
            if(a[i] - b[i] != val && b[i] - a[i] != val)
                break;
        if(i == n)
        {
            printf("TAK
1 %d %d
" , n , val);
            for(i = 2 ; i < n ; i ++ )
            {
                if(a[i] < b[i]) printf("1 %d %d
" , i , a[i]);
                else printf("%d %d %d
" , n , i , b[i]);
            }
            return 0;
        }
    }
    v[++tot] = data(0 , 1);
    for(i = 2 ; i < n ; i ++ )
        if(l[i] == len)
            v[++tot] = data(a[i] , i);
    v[++tot] = data(len , n);
    sort(v + 1 , v + tot + 1);
    for(i = 1 ; i < tot ; i ++ )
    {
        if(v[i].d == v[i + 1].d)
        {
            puts("NIE");
            return 0;
        }
        x[++cnt] = v[i].p , y[cnt] = v[i + 1].p , z[cnt] = v[i + 1].d - v[i].d;
    }
    for(i = 2 ; i < n ; i ++ )
    {
        if(l[i] != len)
        {
            if((l[i] - len) & 1 || 
               (t = lower_bound(v + 1 , v + tot + 1 , data(a[i] - ((l[i] - len) >> 1) , 0)) - v) > tot || 
                v[t].d != a[i] - ((l[i] - len) >> 1))
            {
                puts("NIE");
                return 0;
            }
            x[++cnt] = v[t].p , y[cnt] = i , z[cnt] = (l[i] - len) >> 1;
        }
    }
    puts("TAK");
    for(i = 1 ; i <= cnt ; i ++ ) printf("%d %d %d
" , x[i] , y[i] , z[i]);
    return 0;
}