这是一篇发布于 1250 天以前的旧文

这是一篇发布于 1250 天以前的旧文。其中的部分内容可能已经过时。

int cnt=0;

vector ret=vec;

迷宫的一些格子里有石头。当你移动到有石头的格子时，石头就会按你移动的方向被推到下一个格子。如果下一个格子里有石头，它就会被推得更远，以此类推。迷宫被不可穿透的墙壁所包围，因此任何将你或任何石头移出迷宫的行为都是非法的。

求出起点到终点路径数量，对 $10^9+7$ 取模。

考虑到以这种定义走到 $ij$ 的时候，右下角能到达的石头位置都没有改变过；所以 $ij$ 的状态可以独立考虑，和经过的路径无关。

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

for (int j=1;j<=m;j++)

for (int j=m;j>=1;j--)

for (int i=n;i>=1;i--)

你需要构造一条链，赋予链上每个点 $[0n-1]$ 的标号，并且在对这个链进行 $k$ 次操作后，其形态和给出的树完全相同。

输出一种链上点的标号方案，然后输出操作次数和一种操作方案。操作次数不能大于 $10^6$ 的。保证有解。

考虑反着做，把给定的树变成一条链。如果每次操作都能使树的深度增加 1，那么我们最多只需要做 $n-1$ 次，满足答案的限制。那么考虑如何让每次操作都使深度加 1。

首先贪心地想，肯定选取树中从根节点出发的最长的一条路径作为链的基础，其他操作在剩余的点上完成。如果这条路径上所有节点都没有大于一个儿子，则已经做完了；否则找出一个有至少两个儿子的点 $x$，假设其一个在路径上的点是 $u$，另一个不在路径上的点是 $v$，我们另 $u$ 的父亲变成 $v$，就实现了深度增加。

具体实现，对最深的分叉点，把这个节点的所有儿子一个个合并。

cnt=0;

请勿填写无意义邮箱或发表无关评论，否则会被视为垃圾评论。