bzoj5100 [POI2018]Plan metra 构造

2021-09-05 02:43:57

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<<];

inline char gc(){

    static char s[],*p1,*p2;

    if(p1==p2)p2=(p1=s)+fread(s,,,stdin);

    if(p1==p2)return EOF;return *p1++;

}

inline int read(){

    int x=;char ch=gc();

    while(ch<''||ch>'')ch=gc();

    while(ch>=''&&ch<='')x=x*+ch-'',ch=gc();

    return x;

}

inline int solve1(){

    int dis=abs(d1[]-dn[]);

    if(!dis)return ;

    for(register int i=;i<n;++i)

    if(dis!=abs(d1[i]-dn[i]))return ;

    puts("TAK");printf("%d %d %d\n",,n,dis);

    for(register int i=;i<n;++i){

        if(d1[i]<dn[i])printf("%d %d %d\n",i,,d1[i]);

        else printf("%d %d %d\n",i,n,dn[i]);

    }

    return ;

}

int main(){

    n=read();if(n==){puts("TAK\n1 2 1");return ;}

    for(register int i=;i<n;++i)d1[i]=read();

    for(register int i=;i<n;++i){

        dn[i]=read();

        dn[i]+d1[i]<mn?mn=dn[i]+d1[i]:;

    }

    if(solve1())return ;

    id[mn]=n;id[]=;

    for(register int i=;i<n&&!fg;++i){

        if(dn[i]+d1[i]==mn){

            if(id[d1[i]])fg=;

            else id[d1[i]]=i;

        }

    }

    if(fg){puts("NIE");return ;}

    for(register int i=;i<n&&!fg;++i){

        if(d1[i]+dn[i]==mn)continue;

        int tmp=d1[i],len=d1[i]+dn[i]-mn;

        if(len&)fg=;len>>=;

        tmp-=len;if(!id[tmp])fg=;

        fa[i]=id[tmp];w[i]=len;

    }

    if(fg){puts("NIE");return ;}

    int pre=;puts("TAK");

    for(register int i=;i<=mn;++i){

        if(!id[i])continue;

        printf("%d %d %d\n",pre,id[i],i-d1[pre]);

        pre=id[i];

    }

    for(register int i=;i<n;++i){

        if(!fa[i])continue;

        printf("%d %d %d\n",i,fa[i],w[i]);

    }

    return ;

}

码农公寓