【墨西哥区域赛】Carpet

原题：

题意：

给你一个树，有1e5个节点，让你把这个树放在一个长1e6宽20的网格图里，要求一个格子放一个节点，树边之间不能相交

这是一道构造题

因为树的形状可能性很多，很复杂，所以不能简单猜测，而必须要依据某种性质，来保证生成的解一定合法

先尝试小规模，或特殊的问题也是一个重要的思想方法

首先考虑一个节点A和它的所有儿子

不难发现，这时可以把这个节点放在某层，然后把它的儿子放在下一层的一个区间内

只要爸爸出现的顺序和儿子所在区间出现的顺序相同，就不会发生冲突

因为在两层之间连边，斜率只会无限趋于0，所以不会出现于(xA, yA+1)和(xA, yA-1)冲突的情况，只需保证这两层之间的边不相交

继而可以发现，只要满足这个条件，不管A和它的儿子们在什么位置，都不会和别人冲突

为了压缩空间，所有的儿子可以连续放在一起，即使和爸爸相距太远也没有问题

其次，题目数据中宽度为20

根据经验，与众不同的数字往往有重要含义

可以敏感地发现20刚好是log1e6

联系到树链剖分

因为重链剖分保证任意一个节点到根节点的路径最多只会经过logn条重链

所以可以让一条重链躺在一层，而轻儿子都放到下一层，根节点放左上角

这样对于任意一点，想要通过构造的网格图去往根节点，至多会往上爬logn层

所以深度不会超过限制，而宽度显然充足

所以问题就解决了

轻儿子放在连续的区间，区间出现的顺序和爸爸出现的顺序相同，这能保证不发生冲突

进行树链剖分，重链剖分的性质保证深度不会超过限制

代码：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 using namespace std;

 int rd(){int z=;  char ch=getchar();

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

     while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-'';  ch=getchar();}

     return z;

 }

 struct edg{int y,nxt;}e[];  int lk[],ltp=;

 void ist(int x,int y){

     e[++ltp]=(edg){y,lk[x]};  lk[x]=ltp;

     e[++ltp]=(edg){x,lk[y]};  lk[y]=ltp;

 }

 int n;

 int fth[],hvc[],sz[];

 int ax[],ay[];

 int hd[];

 void dfs1(int x,int y){

     fth[x]=y;  sz[x]=;

     int mx=,mxid=;

     for(int i=lk[x];i;i=e[i].nxt)if(e[i].y!=y){

         dfs1(e[i].y,x);

         sz[x]+=sz[e[i].y];

         if(sz[e[i].y]>mx)  mx=sz[e[i].y],mxid=e[i].y;

     }

     hvc[x]=mxid;

 }

 void dfs(int x,int y){

     ay[x]=y,ax[x]=++hd[y];

     for(int i=lk[x];i;i=e[i].nxt)if(e[i].y!=fth[x] && e[i].y!=hvc[x])

         dfs(e[i].y,y+);

     if(hvc[x])  dfs(hvc[x],y);

 }

 int main(){

     //freopen("ddd.in","r",stdin);

     memset(lk,,sizeof(lk));

     memset(hd,,sizeof(hd));

     cin>>n;

     int l,r;

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

         l=rd(),r=rd();

         ist(l,r);

     }

     dfs1(,);

     dfs(,);

     for(int i=;i<=n;++i)  printf("%d %d\n",ax[i],ay[i]);

     return ;

 }

巴特西

【墨西哥区域赛】Carpet

最新文章

热门文章