{"problem":{"name":"[PA 2018] Poddrzewo","description":{"content":"**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 1 [Poddrzewo](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/pod/)** 给定一个长度为 $n$ 的序列 $a$。 构造一个结点数为 $k$ 的无根树，结点编号分别为 $1 \\cdots k$。该树第","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9077"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Runda 1 [Poddrzewo](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/pod/)**\n\n给定一个长度为 $n$ 的序列 $a$。\n\n构造一个结点数为 $k$ 的无根树，结点编号分别为 $1 \\cdots k$。该树第 $i$ 个结点的度数为 $a_i$。\n\n有可能无解，你可以进行如下操作来使其有解：\n\n1. 修改序列中第 $i$ 个数。\n1. 删除序列中第 $i$ 个数。\n1. 交换序列中第 $i,j$ 个数。\n\n可以证明，进行有限次操作后一定有解。\n\n你的任务是 **最小化操作 $1$ 使用的次数**。\n\n## Input\n\n一行一个整数 $n$，表示序列 $a$ 的长度。\n\n下一行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。\n\n## Output\n\n第一行一个整数 $x$ ，表示操作 $1$ 使用次数最小值。\n\n第二行一个整数 $k\\ (2 \\le k \\le n)$，表示你构造的树结点数目。\n\n接下来 $k-1$ 行，每行两个数 $u,v\\ (1 \\le u, v \\le k)$，表示连接第 $u,v$ 个结点。\n\n多解输出任意解。\n\n[samples]\n\n## Note\n\n#### 样例 1 解释\n\n我们可以删除第 $3$ 个数字，然后更改元素的顺序。\n\n得到最后的序列为 $(3,2,1,1,1)$。\n\n这是构造的树的示意图：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ptch7dx0.png)\n\n------------\n\n#### 样例 2 解释\n\n我们可以修改第 $3$ 个数字，得到最后的序列为 $(1,2,1)$。可以证明，操作 $1$ 至少需要使用 $1$ 次。\n\n这是构造的树的示意图：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/o6mhe76c.png)\n\n------------\n\n#### 数据范围\n\n**本题采用捆绑测试**\n\n对于 $100\\%$ 的数据：\n\n- $2 \\le n \\le 10^6$\n- $1 \\le a_i \\le n-1$\n\n保证存在至少一个子任务，其中操作 $1$ 使用次数最小值为 $0$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9077","tags":["2018","Special Judge","PA（波兰）"],"sample_group":[["6\n2 1 5 3 1 1","0\n5\n1 2\n2 3\n1 4\n1 5"],["3\n1 2 2","1\n3\n1 2\n2 3"]],"created_at":"2026-03-03 11:09:25"}}