P13078 [NOISG 2019] Rigged Roads

Silvermill 最近财政紧张，市长 Peanut 打算拆除部分道路以节省养护成本。

Silvermill 可以看作一个城市，包含 $N$ 个道路交汇点和 $E$ 条道路，第 $i$ 条道路连接交汇点 $A_i$ 和 $B_i$。交汇点编号为 $1$ 到 $N$，道路编号为 $1$ 到 $E$。保证任意两个交汇点之间总可以直接或间接到达，且没有两条道路连接同一对交汇点。 为了方便决策，Peanut 请你帮忙评估各条道路的养护成本。你的任务是： 你需要给出一个长度为 $E$ 的排列 $W = (W_1, W_2, \dots, W_E)$，表示第 $i$ 条道路的养护成本为 $W_i$，其中 $W$ 是 $1$ 到 $E$ 的一个排列。 Peanut 会根据你提供的养护成本，保留一组道路，满足： - 所有交汇点仍然连通； - 保留道路的养护成本之和最小。 即，Peanut 实际上会选择最小生成树，且由于所有成本互不相同，最小生成树唯一。 但你另有所图。你想让最终被保留的道路集合恰好是你指定的一组道路 $R$，且 $R$ 恰好构成一棵生成树。通过合理选择 $W$，你可以让 $R$ 恰好成为最小生成树。 请你计算，满足上述条件的字典序最小的排列 $W$。 给定城市结构和你想保留的道路集合 $R$，请输出字典序最小的养护成本分配方案 $W$，使得 $R$ 成为唯一的最小生成树。 注：若存在第 $1 \leq p \leq E$ 使得 $W_p < W'_p$，且 $W_1 = W'_1, \dots, W_{p-1} = W'_{p-1}$，则 $W$ 的字典序小于 $W'$。

第一行包含两个整数 $N$ 和 $E$。 接下来 $E$ 行，每行两个整数 $A_i$ 和 $B_i$，表示第 $i$ 条道路连接的两个交汇点。 最后一行包含 $N - 1$ 个整数，表示你想保留的道路编号，构成的集合 $R$。

输出 $E$ 个整数，表示字典序最小的排列 $W$，第 $i$ 个数是第 $i$ 条道路的养护成本。

【数据范围】 - $1 \leq N, E \leq 3 \times 10^5$ - $1 \leq A_i \neq B_i \leq N$ - $1 \leq R_i \leq E$ - 仅使用 $R$ 中的道路也能保证所有交汇点连通。 | 子任务编号 | 分值 | 额外限制 | | :---: | :---: | :---: | | $1$ | $8$ | $1 \leq N, E \leq 9$ | | $2$ | $19$ | $1 \leq N, E \leq 10^3$ | | $3$ | $9$ | $A_{R_i} = 1,\ B_{R_i} = i + 1$，即 $R$ 构成一棵星形树 | | $4$ | $10$ | $A_{R_i} = i,\ B_{R_i} = i + 1$，即 $R$ 构成一条链 | | $5$ | $10$ | $E = N,\ A_i = i,\ B_i = i \bmod N + 1$ | | $6$ | $12$ | $E = N$ | | $7$ | $32$ | 无额外限制 |