题解：P13537 [IOI 2025] 世界地图（worldmap）

· · 题解

如果是树的话，其实很难想到直接欧拉序可以做到 2n 小一点，行数是 1。但是我们可以做到更差！ 其实就是人类的思考过程：把每个子树包裹起来变成一个矩形。考虑归纳构造，构造一个子树的矩形，先把根放在最外层，然后把每个儿子的矩形依次放进去，中间用根隔开。例如：

111111111
122213331
122213331
122213331

其中 2 和 3 代表两棵儿子子树，1 是根。

这样子的长度是 2n-1，高度是树的深度。其实最后一行就是欧拉序。

考虑能不能取一个生成树，把剩下的边塞进去。既然是任意生成树那就取 dfs 树。很难想到可以把上面的结构弄松一点变成这样：

111111111
1?1?1?1?1
111111111
122213331
122213331
122213331

这样子就是每个子树的根处扩展成一个中空的包裹，可以用来塞点东西。这个包裹的大小大概是子树大小，所以对于每条返祖边，你把这条边深度大的点放到它祖先的包裹里即可。这样子高度是 3\times dep，长度还是 2n-1。可以获得 86 分的好成绩。

我们直观地感觉这个三层铺的有点浪费，观察一个例子：

11111111111
1?1?1?1?1?1
11111111111
12222222131
12?2?2?2131
12222222131
12444252131
124?4252131
12444252131
12464252131

其实可以发现对于相邻的两层（第 3a+b 行和第 3(a+1)+b 行，b=1,2,3），它们的 ? 的间隔开来的。对于如下左边的结构，其实可以变成右边：

111    1
1?1   1?1
111    1

节约掉四个角的空间之后，可以发现相邻两层解决掉的空间刚好是一奇一偶，正好可以岔开，所以上图就可以变成（只画前两层）：

1?1?1?1?1?1   1?1?1?1?1?1
11 1 1 1111   11212121111
1 2 2 2 131   12?2?2?2131
12?2?2?2131

这样每个深度就被压缩成了两层。顺便把第一行删掉。最后是 (2n-1)\times (2n-1)。


#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
#define MOD         998244353
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
#define lowbit(x)   ((x)&(-(x)))
#define cntbit(x)   __builtin_popcount(x)
#define deal(v)     sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
#define lbound(v,x) lower_bound(all(v),x)-v.begin()
vector<vector<int>>ans;
vector<int>v[50],g[50];
int vis[50],fa[50],sz[50],dep[50];
void dfs(int x,int pre,int d){
    vis[x]=1;dep[x]=d;sz[x]=1;
    for(auto i:v[x])if(i!=pre){
        if(!vis[i]){
            fa[i]=x;
            g[x].pb(i);g[i].pb(x);
            dfs(i,x,d+1);
            sz[x]+=sz[i];
        }
    }
}
pii pos[50];
void color(int x,int pre,int l,int r,int d){
    REP(i,l,r+1)ans[d*2][i]=x;
    REP(i,l,r+1)if((i-l)&1){ans[d*2+1][i]=x;if(d)ans[d*2-1][i]=x;}
    pos[x]={d*2,l+1};
    for(auto i:g[x])if(i!=pre){
        ++l;
        color(i,x,l,l+sz[i]*2-2,d+1);
        l+=sz[i]*2-1;
    }
}
vector<vector<int>>create_map(int n,int m,vector<int>U,vector<int>V){
    ans=vector<vector<int>>(n*2-1,vector<int>(n*2-1,0));
    REP(i,1,n+1)v[i].clear(),vis[i]=0,g[i].clear();
    REP(i,0,m)v[U[i]].pb(V[i]),v[V[i]].pb(U[i]);
    dfs(1,0,0);
    color(1,0,0,2*n-2,0);
    REP(i,1,n+1){
        for(auto j:v[i])if(dep[j]>dep[i]&&fa[j]!=i){
            auto &[x,y]=pos[i];
            ans[x][y]=j;
            y+=2;
        }
    }
    REP(i,0,n*2-1){
        REP(j,0,n*2-1)if(!ans[i][j]){
            if(i)ans[i][j]=ans[i-1][j];
            else ans[i][j]=ans[i][j-1];
        }
    }
    return ans;
}