{"problem":{"name":"异界之门","description":{"content":"嗅觉敏锐的莲子察觉到，进入异界的方法一定和这些特别的地藏有所联系。她发现它们恰好构成了一棵形状特殊的树。 给定一棵 $n$ 个点的带点权的**有根**树，其根为 $1$，且点 $i$ 的点权为 $w_i$。**其满足对于任意两个深度相同的结点，它们的儿子数也相同**。 为了进入异界，莲子进行了一些操作来改变这棵树的点权： 1. 选择一条边，假设它连接了两点 $(u,v)$，设其中深度更高者为","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10610"},"statements":[{"statement_type":"Markdown","content":"嗅觉敏锐的莲子察觉到，进入异界的方法一定和这些特别的地藏有所联系。她发现它们恰好构成了一棵形状特殊的树。\n\n给定一棵 $n$ 个点的带点权的**有根**树，其根为 $1$，且点 $i$ 的点权为 $w_i$。**其满足对于任意两个深度相同的结点，它们的儿子数也相同**。\n\n为了进入异界，莲子进行了一些操作来改变这棵树的点权：\n\n1. 选择一条边，假设它连接了两点 $(u,v)$，设其中深度更高者为 $u$（即 $u$ 是 $v$ 的儿子），将 $w_u$ 加上 $w_v$。\n2. 上述操作可以被执行任意多次，但是**不能重复选择同一条边**。\n\n经过操作后，莲子求出了树的某个 [DFS 序列](https://oi-wiki.org/graph/dfs/)，并记录下了这个 DFS 序列所对应的点权序列 $c$（具体来说，$c_i$ 为 DFS 序过程中遍历到的第 $i$ 个点的点权）。\n\n不幸的是，她突然忘记了她进行过哪些操作，也忘记了如何 DFS 这棵树，她希望你能还原出任意一组合法的操作方案与 DFS 序列。\n\n## Input\n\n第一行一个整数 $n$。\n\n对于接下来 $n$ 行：第 $i$ 行两个整数 $f_i,w_i$，其中 $f_i$ 代表点 $i$ 的父节点（特别的，$f_1=0$，对于其余节点有 $1\\le f_i<i$），$w_i$ 代表点 $i$ 的权值。\n\n接下来一行 $n$ 个整数描述序列 $c$，代表莲子的 DFS 序列所对应的点权序列 $c$。保证一定存在一种合法的操作方式和操作后的 DFS 方式得到序列 $c$。\n\n## Output\n\n第一行一个整数 $m$，表示你进行的操作数。\n\n接下来一行 $m$ 个数，第 $i$ 个数 $x_i$ 代表你在第 $i$ 次操作选择连接节点 $x_i$ 和其父节点 $f_{x_i}$ 的边进行操作。\n\n接下来一行 $n$ 个数描述一个排列 $p$，其中 $p_i$ 代表你构造的 DFS 序列中遍历到的第 $i$ 个节点为点 $p_i$。\n\n[samples]\n\n## Background\n\n跟随着线索，莲子来到了七夕坂。无暇欣赏此处的风景，高速运转着大脑的莲子，不断寻找异界的线索。翻转的地藏、奇异的裂缝、被隐匿的第五个季节……这个禁忌之中的世界，正向她揭晓着自己的秘密。\n\n但莲子第一时间看到的只有梅莉，来不及思考，她一把抓住了梅莉的手——\n\n## Note\n\n### 样例解释\n\n#### 样例 \\#1\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ihq8vqnc.png)\n\n其中一种可行的方案是依次操作边 $(2,3),(3,4),(1,2)$，操作后的树的点权序列为 $\\{1,3,5,9\\}$，选出的 DFS 序列为 $\\{1,2,3,4\\}$。\n\n注意到该样例符合特殊性质 $\\mathbf{A}$。\n\n#### 样例 \\#2\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/z14j0aeu.png)\n\n其中一种可行的方案是依次操作边 $(1,2),(3,5),(1,3)$，操作后的树的点权序列为 $\\{1,0,0,3,3\\}$，选出的 DFS 序列为 $\\{1,2,4,3,5\\}$。\n#### 样例 \\#3\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/7livbzzu.png)\n\n其中一种可行的方案是依次操作边 $(1,2)$，操作后的树的点权序列为 $\\{1,3,3,4\\}$，选出的 DFS 序列为 $\\{1,4,2,3\\}$。\n\n注意到该样例符合特殊性质 $\\mathbf{B}$。\n#### 样例 \\#4\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/9bopbeh3.png)\n\n其中一种可行的方案是依次操作边 $(1,2),(2,4),(3,5),(1,3)$，操作后的树的点权序列为 $\\{1,2,3,2,2\\}$，选出的 DFS 序列为 $\\{1,3,5,2,4\\}$。\n\n注意到该样例符合特殊性质 $\\mathbf{C}$。\n\n### 数据范围\n\n**本题采用捆绑测试。**\n\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{|c|c|c|c|c|}\\hline\n\\textbf{Subtask} & \\textbf{\\textsf{分值}} & \\bm{n\\le } & \\textbf{\\textsf{特殊性质}}&\\textbf{Subtask \\textsf{依赖}}\\cr\\hline\n1 & 10 & 6 & - &-\\cr\\hline\n2 & 10 & 100 & \\mathbf{A}&- \\cr\\hline\n3 & 10 & 100 & \\mathbf{B}&- \\cr\\hline\n4 & 15 & 2\\times 10^3 & \\mathbf{C}&-  \\cr\\hline\n5 & 15 & 2\\times 10^3 & \\mathbf{D}&-  \\cr\\hline\n6 & 15 & 100 & -&1,2,3  \\cr\\hline\n7 & 25 & 2\\times 10^3 & -&1,2,3,4,5,6  \\cr\\hline\n\\end{array}\n$$\n\n特殊性质 $\\mathbf{A}$：保证给出的树满足 $f_i=i-1$ ($i\\ne 1$)。\\\n特殊性质 $\\mathbf{B}$：保证给出的树满足 $f_i=1$ ($i\\ne 1$)。\\\n特殊性质 $\\mathbf{C}$：保证给出的树满足 $w_i=1$。\\\n特殊性质 $\\mathbf{D}$：保证给出的树满足所有非叶节点儿子数不超过 $2$。\n\n对于所有数据满足：$1\\le n\\le 2000$，$-10^8\\le w_i\\le 10^8$，$-10^{14}\\le c_i\\le 10^{14}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10610","tags":["洛谷原创","Special Judge","O2优化","二分图","洛谷月赛"],"sample_group":[["4\n0 1\n1 2\n2 3\n3 4\n1 3 5 9","3\n3 4 2\n1 2 3 4"],["5\n0 1\n1 -1\n1 -1\n2 3\n3 4\n1 0 3 0 3","3\n2 5 3\n1 2 4 3 5"],["4\n0 1\n1 2\n1 3\n1 4\n1 4 3 3","1\n2\n1 4 2 3"],["5\n0 1\n1 1\n1 1\n2 1\n3 1\n1 2 2 2 3","4\n2 4 5 3\n1 3 5 2 4"]],"created_at":"2026-03-03 11:09:25"}}