拉篇题解。
设 $p_{i,j}$ 表示 $i$ 号点的第 $j$ 维坐标。（$i\in [1,n],j\in [1,m]$）
先从一些简单情况入手：
- 只有一条链（假设是 $1 \to 2 \to 3...\to n$ 类似的样子）我们可以映射到一维空间一段区间上（$x_{i,1}=x_{i-1,1}+1$）。
而由于曼哈顿距离的特性，每一维是相互独立的，而每一维看上去可以放一个区间。那么我们猜测可能是为每一维分配一条链，在一条链上移动可能就是在对应的维度上加减一。
手摸一下比较简单的情况：假设这么一颗树： $2\to 1\to 3,4\to 1 \to 5$ 已经划分好了两条链，为每条链分配一个维度，那么 $d(2,3)$ 可以解释为：在 $2\to 1\to 3$ 对应的维度上走两步；$d(2,5)$ 可以解释为：先在链 $2\to 1\to 3$ 对应的维度上走一步到 $1$，再从链 $4\to 1 \to 5$ 对应的维度上走一步。
如果两条链没有交，我们发现我们的构造就寄掉了，这要求我们强制钦定他们有交。
我们先掠过构造链的过程，假设我们已经划分出来 $m$ 条链，其中第 $i$ 条链与前 $i-1$ 条链中的至少一条存在交集。那么我们采用归纳法证明存在合法的构造方案：
假设对于前 $i-1$ 条链组成的树，任意两个点的 $d$ 等于他们的曼哈顿距离。
对于第 $i$ 条链，我们这么构造：
那么构造完之后，考虑 $d(i,j)$ 是否满足条件：
- 如果 $x,y\in p\to q$，那么显然成立。
- 如果 $x\in p\to q,y\not \in p\to q$，那么找到 $r$ 满足 $r\in x\to y,r\in 交集$ 且在满足前面的情况下 $r$ 距离 $i$ 最近。那么我们把路径拆成 $x\to r$ 和 $r\to y$ 两个路径，可以看出由于构造，$d(x,r)=x 到 r 的曼哈顿距离$，$d(r,y)=r 到 y 的曼哈顿距离$，并且由于 $x$ 和 $r$ 的前 $i-1$ 维相同，$r$ 和 $y$ 的第 $i$ 维相同，那么 $x 到 y 的曼哈顿距离=x到r的曼哈顿距离+r到y的曼哈顿距离$。那么成立。
剩下的问题就是找到最小的 $m$ 和选取满足条件的 $m$ 条链。
既然是树上选链那么我们可以把链沿伸到叶子，由于一条链最多占两个叶子，所有叶子必须被链覆盖，所以我们猜测下界就是 $\lceil\frac{叶子数量}{2}\rceil$。证明：
显然，因为对于一条边上的两个点，其曼哈顿距离为 $1$，即他们的坐标在某一维加减一，我们可以看作把这条边有方向的分配到某个维度：如果对于边 $(x,y)$，我们让其方向指向 $x\to y$，这说明 $y$ 有且存在某一维坐标比 $x$ 的这一维坐标大一。我们看作边 $(x,y)$ 属于维度 $E_{(x,y)}$。
显然，对于 $d(x,y)$，有：$d(x,y)=\sum_{i=1}^{m}\sum_{(a,b)\in x\to y}[E_{(a,b)}=i]=|\sum_{i=1}^{m}p_{x,i}-p_{y,i}|$，第一个等号是因为 $d(x,y)$ 恰好等于路径上的边数。
因为对于边 $(a,b)$ 只会有：$p_{a,E_{a,b}}-p_{b,E_{a,b}}=\pm 1,p_{a,j}=p_{b,j},j\not =E_{a,b}$，所以有 $\sum_{(a,b)\in x\to y}[E_{(a,b)}=i]\le |p_{x,E_{(a,b)}}-p_{y,E_{(a,b)}}|$，结合上面的式子可以推出 $\sum_{(a,b)\in x\to y}[E_{(a,b)}=i]= |p_{x,E_{(a,b)}}-p_{y,E_{(a,b)}}|$，又因为 $E_{(a,b)}$ 只会使 $E_{(a,b)}$ 维度上的值加减一，想要做到等号，必须保证每条边对于这个维度上的影响都是正号或者都是负号。
也就是说，对于任意一个维度，对于任意一条路径 $x\to y$，经过的在这个维度里的边必须都顺着一个方向。
那么可以看出，对于任意一个维度里的所有边，他们必须在一条链上，否则就能推出矛盾：
假设对于一个维度 $i$ 那么我们可以找到一个点 $C$，使得点 $C$ 至少存在三个子树含有在维度 $i$ 里的边。如果我们把 $C$ 看作父亲，设 $(a_1,b_1),(a_2,b_2),(a_3,b_3)$ 在 $C$ 的三个不同子树内，且 $b_j$ 是 $a_j$ 的父亲。 那么：
对于路径 $a_1\to a_2$，要求 $(a_1,b_1),(a_2,b_2)$ 有一个指向父亲，有一个指向儿子。
对于路径 $a_1\to a_3$，要求 $(a_1,b_1),(a_3,b_3)$ 有一个指向父亲，有一个指向儿子。
即要么是：$a_1\to b_1,b_2\to a_2,b_3\to a_3$，要么是：$b_1\to a_1,a_2 \to b_2,a_3\to b_3$。
对于路径 $a_2\to a_3$，要求 $(a_2,b_2),(a_3,b_3)$ 有一个指向父亲，有一个指向儿子，和上述矛盾。
即这种情况并不合法
那么问题转化成用链覆盖树，显然的一个树至少需要 $\lceil\frac{叶子数量}{2}\rceil$ 条链被覆盖，那么下界至少是这么多。
最后一个问题是怎么构造这 $m$ 条链，采用简单一点的方法：
- 我们把叶子节点的权值看作 $1$，非叶节点的权值看作 $0$，求出此时的带权重心 $rt$。那么对于 $rt$ 的每一个子树，其叶子节点个数乘 $2$ 小于等于总叶子个数。
- 我们按 $dfn$ 序抽出叶子节点（设组成的数组为 $lf$），那么在同一个子树内的叶子节点在一段连续的区间上。由于这个区间的长度乘 $2$ 小于等于总区间长度，那么 $lf_x$ 和 $lf_{x+\lceil\frac{叶子数量}{2}\rceil}$ 这两个点不属于同一棵子树
- 我们两两匹配这些点，显然，这些链都经过根节点，且经过了所有点，就满足了上面的条件了。
- 如果叶子节点是奇数，我们取根到最后一个叶子作为一段路径就可以了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+100;
int n,rt;
vector<int>g[N],lf,p[N];
int cnt[N],mx[N],fa[N],dep[N],vis[N];
void dfs(int x)
{
dep[x]=dep[fa[x]]+1;
if(g[x].size()==1)cnt[x]=1;
if(g[x].size()==1)lf.push_back(x);
for(auto y:g[x])if(y!=fa[x])fa[y]=x,dfs(y),mx[x]=max(mx[x],cnt[y]),cnt[x]+=cnt[y];
}
void work(int x,int i,int v)
{
if(vis[x])return;
work(fa[x],i,v);
p[x]=p[fa[x]];p[x][i]+=v;
vis[x]=1;
}
signed main()
{
cin>>n;
if(n==1){cout<<1<<endl<<0<<endl;return 0;}
for(int i=1;i<n;i++){int x,y;cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}
dfs(1);
for(int i=1;i<=n;i++)if(max(mx[i],cnt[1]-cnt[i])*2<=cnt[1]){rt=i;break;}
lf.clear();fa[rt]=0;dfs(rt);
int m=(lf.size()+1)>>1;
for(int i=1;i<=n;i++)p[i].resize(m);
vis[rt]=1;
for(int i=0;i<m;i++)
{
int x=lf[i];
work(x,i,1);
if(i+m<lf.size())work(lf[i+m],i,-1);
}
cout<<m<<endl;
for(int i=1;i<=n;i++,cout<<endl)for(auto x:p[i])cout<<x<<" ";
return 0;
}