{"problem":{"name":"[CEOI 2022] Drawing","description":{"content":"给定平面上的 $N$ 个点，和一棵大小为 $N$ 的树 $T$，保证这棵树上每个点的度数至多为 $3$，树上节点按 $1\\sim N$ 编号。 你需要为平面上的点使用 $1\\sim N$ 的编号重编号之后，对于所有树上的边 $e=(u,v)$，将平面上的点 $u$ 和平面上的点 $v$ 用线段连接后，任意两条线段除了在端点上相交没有其他的相交点。 试构造一组方案，保证一定有解。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8999"},"statements":[{"statement_type":"Markdown","content":"给定平面上的 $N$ 个点，和一棵大小为 $N$ 的树 $T$，保证这棵树上每个点的度数至多为 $3$，树上节点按 $1\\sim N$ 编号。\n\n你需要为平面上的点使用 $1\\sim N$ 的编号重编号之后，对于所有树上的边 $e=(u,v)$，将平面上的点 $u$ 和平面上的点 $v$ 用线段连接后，任意两条线段除了在端点上相交没有其他的相交点。\n\n试构造一组方案，保证一定有解。\n\n## Input\n\n第一行一个整数 $N$。\n\n接下来 $N-1$ 行，一行两个整数 $a,b$，表示有一条从 $a$ 连向 $b$ 的边。\n\n接下来 $N$ 行，一行两个整数 $x,y$，表示一个点的横纵坐标为 $(x,y)$。保证这 $N$ 个点两两不同，且没有任意三点共线。\n\n## Output\n\n输出一行 $N$ 个整数，第 $i$ 个数应为原本的第 $i$ 个点的标号。\n\n[samples]\n\n## Note\n\n### 样例 3 解释\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/1sz6z9sk.png)\n\n蓝色数字表示所分配的编号，黑色数字表示原本的编号。\n\n### 数据规模与约定\n\n对于所有数据，保证 $0\\le x,y\\le 10^9$。\n\n| Subtask 编号 |                 特殊限制                  | 分数 |\n| :----------: | :--------------------------------------: | :--: |\n|     $1$      | $3\\le N\\le 2\\times 10^5$，所有点均在凸包上 | $10$ |\n|     $2$      |             $1\\le N\\le 4000$             | $15$ |\n|     $3$      |             $1\\le N\\le 10^4$             | $15$ |\n|     $4$      |         $1\\le N\\le 8\\times 10^4$         | $35$ |\n|     $5$      |         $1\\le N\\le 2\\times 10^5$         | $25$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8999","tags":["2022","Special Judge","CEOI（中欧）"],"sample_group":[["3\n1 2\n2 3\n10 10\n10 20\n20 10","1 2 3"],["5\n1 2\n1 3\n1 4\n4 5\n10 10\n10 30\n30 10\n30 30\n20 25","5 4 2 3 1"],["6\n1 2\n2 3\n1 4\n4 5\n4 6\n10 60\n10 40\n40 50\n40 30\n70 30\n70 10","6 5 4 1 2 3"]],"created_at":"2026-03-03 11:09:25"}}