CF761E Dasha and Puzzle

Dasha 在解决完问题后，决定休息一下。她准备开始最喜欢的活动——折纸，但又想起了自己没能解决的谜题。 树是一种无向连通且无环的图。特别地，在一个包含 $n$ 个顶点的树中总共有 $n-1$ 条边。 这个谜题要求你把树的顶点放置在平面直角坐标系的整点上，使得所有通过树中边连接的顶点组成的线段都平行于坐标轴。同时，线段之间只允许在端点处相交。不同的顶点应当放在不同的点上。 请帮助 Dasha 找到一种合适的方法，将树的顶点放在平面上。 保证如果存在一种合法的放置方法使得满足题中给定的条件，那么你总可以仅使用绝对值不超过 $10^{18}$ 的整点坐标进行放置。

第一行包含一个整数 $n$ $(1 \leq n \leq 30)$，表示树的顶点个数。 接下来的 $n-1$ 行，每行包含两个整数 $u_i, v_i$ $(1 \leq u_i, v_i \leq n)$，表示第 $i$ 条边连接着 $u_i$ 和 $v_i$ 两个顶点。 保证输入的图是一棵树。

如果该谜题无解，则输出一行 "NO"。 否则，第一行输出 "YES"。接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$ $(|x_i|, |y_i| \leq 10^{18})$，表示与第 $i$ 个顶点对应的点的坐标。 如果有多组解，输出其中任意一组即可。

在第一个样例中，树的一种可行放置方式如下图所示： 由 ChatGPT 5 翻译