bzoj5100 [POI2018]Plan metra 构造

5100: [POI2018]Plan metra

Time Limit: 40 Sec Memory Limit: 128 MBSec Special Judge
Submit: 189 Solved: 43
[Submit][Status][Discuss]

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

HINT

Source

鸣谢Claris上传试题

构造题
分情况讨论
1. 1-n路径上没有其他点，即1与n直接相连
如果是这种情况，那么就有：对于任意一个点 i 1<i<n i到1与n的距离之差为一个定值a,a=1到n的边权
特判一下每个点到 1和n的距离差是否相等就好
如果相等，可以直接把1和n相连其它点都与1和n相连
如果不等，进入第二种情况

2. 1-n路径上还有点
我们可以找出这些点这些点有一个共性：它们到1与n的距离和相等且比不在1-n路径上的点到1和n的距离和小
找到这些点之后其他点都可以通过与路径上的点相连来构造答案
如果一个点i与路径上某点相连设它到1的距离为d1 到n的距离为dn

那么它到路径上某点（假设存在）的距离就是 w=（d1+dn-（1-n的距离））/2
/2是因为计算了2次而如果w不能被整除的话，点i不能链接到树上

再判断路径上这个点是否存在，如果路径上不存在这个点，依旧没法把点i链接到树判断条件：到1距离为d1-w的点存在于路径上

这样就一定可以构造出一棵合法树

#include<bits/stdc++.h>
#define N 500005
using namespace std;
int n,fg,mn=0x3f3f3f3f,fa[N],w[N],d1[N],dn[N],id[N<<2];

inline char gc(){
    static char s[1000000],*p1,*p2;
    if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
    if(p1==p2)return EOF;return *p1++; 
}
inline int read(){
    int x=0;char ch=gc();
    while(ch<'0'||ch>'9')ch=gc();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=gc();
    return x; 
}
inline int solve1(){
    int dis=abs(d1[2]-dn[2]);
    if(!dis)return 0;
    for(register int i=3;i<n;++i)
    if(dis!=abs(d1[i]-dn[i]))return 0;
    puts("TAK");printf("%d %d %d
",1,n,dis);
    for(register int i=2;i<n;++i){
        if(d1[i]<dn[i])printf("%d %d %d
",i,1,d1[i]);
        else printf("%d %d %d
",i,n,dn[i]);
    }
    return 1;
}

int main(){
    n=read();if(n==2){puts("TAK
1 2 1");return 0;}
    for(register int i=2;i<n;++i)d1[i]=read();
    for(register int i=2;i<n;++i){
        dn[i]=read();
        dn[i]+d1[i]<mn?mn=dn[i]+d1[i]:1;
    }
    if(solve1())return 0;
    id[mn]=n;id[0]=1;
    for(register int i=2;i<n&&!fg;++i){
        if(dn[i]+d1[i]==mn){
            if(id[d1[i]])fg=1;
            else id[d1[i]]=i;
        }
    }
    if(fg){puts("NIE");return 0;}
    for(register int i=2;i<n&&!fg;++i){
        if(d1[i]+dn[i]==mn)continue;
        int tmp=d1[i],len=d1[i]+dn[i]-mn;
        if(len&1)fg=1;len>>=1;
        tmp-=len;if(!id[tmp])fg=1;
        fa[i]=id[tmp];w[i]=len;
    }
    if(fg){puts("NIE");return 0;}
    int pre=1;puts("TAK");
    for(register int i=1;i<=mn;++i){
        if(!id[i])continue;
        printf("%d %d %d
",pre,id[i],i-d1[pre]);
        pre=id[i];
    }
    for(register int i=2;i<n;++i){
        if(!fa[i])continue;
        printf("%d %d %d
",i,fa[i],w[i]);
    }
    return 0;
}