[COCI 2023/2024 #3] Restorani

Luogu

IDLGP10226

Time2000ms

Memory512MB

DifficultyP6

2023Special JudgeCOCI（克罗地亚）

来到塞格德，Malnar 先生像通常一样，必须了解当地文化，品尝所有传统餐点、特色美食和当地饮料。我们可以把塞格德想象成由 $n - 1$ 条双向道路连接的 $n$ 个景点，这些景点的编号从 $1$ 到 $n$。这样，每一对景点之间都有一条路径。令人惊奇的是，Malnar 先生走过每条道路正好需要一分钟。在景点行走的时间可以忽略不计。 Malnar 先生有一份他想去的 $m$ 家餐厅的清单。它由 $m$ 个正整数组成，其中第 $i$ 个数表示第 $i$ 个餐厅在哪个景点附近。一个问题是 Malnar 先生在餐厅用餐后，必须马上去甜品店吃冰淇淋。另一个问题是，他拒绝两次光顾同一家甜品店。幸运的是他有备而来，因为他知道 $m$ 家甜品店，这些甜品店的位置是由 $m$ 个正整数组成的列表，其中第 $i$ 个数字代表第 $i$ 家甜品店在这个景点附近。 Malnar 先生旅途劳累，不想走更多的路，因此他请你计算一下他需要走多少路，并提供去餐厅和甜品店的顺序，这样他就可以在没有帮助的情况下穿梭于餐厅和甜品店之间了。 Malnar 先生目前在景点 $1$，并且必须在最后回到景点 $1$。 ## Input 第一行包含整数 $n$ 和 $m\ (1\le m\le n\le 3\cdot 10^5)$，分别表示景点个数和餐厅/甜品店个数。第二行包含 $m$ 个整数 $a_i\ (1\le a_i\le n,\forall i\neq j,a_i\neq a_j)$，表示餐厅清单。第二行包含 $m$ 个整数 $b_i\ (1\le b_i\le n,\forall i\neq j,b_i\neq b_j)$，表示甜品店清单。接下来 $n-1$ 行，每行两个整数 $x_i$ 和 $y_i\ (1\le x_i,y_i\le n)$，表示景点 $x_i$ 和 $y_i$ 之间有一条道路。 ## Output 第一行输出 $t$，表示 Malnar 先生为了去所有餐厅和甜品店，并最后返回景点 $1$ 的最短用时。第二行输出 $2m$ 个整数 $v_i$，表示去餐厅和甜品店的顺序。在奇数位置的数表示餐馆，这些数必须组成前 $m$ 个正整数的排列。在偶数位置的数表示甜品店，这些数也必须组成前 $m$ 个正整数的排列。按上述顺序去景点并返回开始位置所经历的时间必须为最短时间 $t$。如果有多个最优顺序，输出任意一个均可。 [samples] ## Background **译自 [COCI 2023/2024 Contest #3](https://hsin.hr/coci/archive/2023_2024) T4「[Restorani](https://hsin.hr/coci/archive/2023_2024/contest3_tasks.pdf)」** ## Note ### 样例解释 1 Malnar 先生首先走一分钟前往唯一在景点 $2$ 的餐厅，然后走两分钟到唯一在景点 $3$ 的甜品店，然后花一分钟走回景点 $1$。Malnar 先生总共会花 $1+2+1=4$ 分钟。 ### 样例解释 2 Malnar 先生按如下顺序去餐厅和甜品店：在景点 $4$ 的餐厅（$2$ 分钟），在景点 $4$ 的甜品店（$0$ 分钟），在景点 $6$ 的餐厅（$3$ 分钟），在景点 $5$ 的甜品店（$1$ 分钟），在景点 $3$ 的餐厅（$1$ 分钟），在景点 $9$ 的甜品店（$3$ 分钟），在景点 $2$ 的餐厅（$3$ 分钟），在景点 $8$ 的甜品店（$3$ 分钟）。在景点 $8$ 处的甜品店吃完冰淇淋后，他返回景点 $1$（$2$ 分钟）。Malnar 先生一共走了 $2+0+3+1+1+3+3+3+2=18$ 分钟。 ### 样例解释 3 Malnar 先生按如下顺序去餐厅和甜品店：在景点 $7$ 的餐厅（$6$ 分钟），在景点 $9$ 的甜品店（$2$ 分钟），在景点 $8$ 的餐厅（$1$ 分钟），在景点 $10$ 的甜品店（$2$ 分钟），在景点 $6$ 的餐厅（$4$ 分钟），在景点 $4$ 的甜品店（$2$ 分钟），在景点 $5$ 的餐厅（$1$ 分钟），在景点 $2$ 的甜品店（$3$ 分钟），在景点 $3$ 的餐厅（$1$ 分钟），在景点 $1$ 的甜品店（$2$ 分钟）。在吃完最后的冰淇淋后，他已经在景点 $1$ 所以他不会移动。Malnar 先生一共走了 $24$ 分钟。 ### 子任务 | 子任务编号 | 附加限制 | 分值 | | :--------: | :------------------------------------: | :--: | | $1$ | $n\le 5\ 000,m\le 10$ | $18$ | | $2$ | $\forall i=1,\ldots,n-1,x_i=i,y_i=i+1$ | $18$ | | $3$ | $n\le 5\ 000$ | $27$ | | $4$ | 无附加限制 | $37$ |

Samples

Input #1

Output #1

4
1 1

Input #2

Output #2

18
3 1 4 2 2 4 1 3

Input #3

Output #3

24
4 4 5 5 3 3 2 2 1 1

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2023/2024 #3] Restorani",
    "description": {
      "content": "来到塞格德，Malnar 先生像通常一样，必须了解当地文化，品尝所有传统餐点、特色美食和当地饮料。 我们可以把塞格德想象成由 $n - 1$ 条双向道路连接的 $n$ 个景点，这些景点的编号从 $1$ 到 $n$。这样，每一对景点之间都有一条路径。令人惊奇的是，Malnar 先生走过每条道路正好需要一分钟。在景点行走的时间可以忽略不计。 Malnar 先生有一份他想去的 $m$ 家餐厅的清单。",
      "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": "LGP10226"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "来到塞格德，Malnar 先生像通常一样，必须了解当地文化，品尝所有传统餐点、特色美食和当地饮料。\n\n我们可以把塞格德想象成由 $n - 1$ 条双向道路连接的 $n$ 个景点，这些景点的编号从 $1$ 到 $n$。这样，每一对景点之间都有一条路径。令人惊奇的是，Malnar 先生走过每条道路正好需要一分钟。在景点行走的时间可以忽略不计。\n\nMalnar 先生有一份他想去的 $m$ 家餐厅的清单。...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments