#P13078. [NOISG 2019] Rigged Roads

    ID: 12878 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>2019NOISG(新加坡)

[NOISG 2019] Rigged Roads

题目背景

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

题目描述

Silvermill 可以看作一个城市,包含 NN 个道路交汇点和 EE 条道路,第 ii 条道路连接交汇点 AiA_iBiB_i。交汇点编号为 11NN,道路编号为 11EE。保证任意两个交汇点之间总可以直接或间接到达,且没有两条道路连接同一对交汇点。

为了方便决策,Peanut 请你帮忙评估各条道路的养护成本。你的任务是:

你需要给出一个长度为 EE 的排列 W=(W1,W2,,WE)W = (W_1, W_2, \dots, W_E),表示第 ii 条道路的养护成本为 WiW_i,其中 WW11EE 的一个排列。

Peanut 会根据你提供的养护成本,保留一组道路,满足:

  • 所有交汇点仍然连通;
  • 保留道路的养护成本之和最小。

即,Peanut 实际上会选择最小生成树,且由于所有成本互不相同,最小生成树唯一。

但你另有所图。你想让最终被保留的道路集合恰好是你指定的一组道路 RR,且 RR 恰好构成一棵生成树。通过合理选择 WW,你可以让 RR 恰好成为最小生成树。

请你计算,满足上述条件的字典序最小的排列 WW

给定城市结构和你想保留的道路集合 RR,请输出字典序最小的养护成本分配方案 WW,使得 RR 成为唯一的最小生成树。

注:若存在第 1pE1 \leq p \leq E 使得 Wp<WpW_p < W'_p,且 W1=W1,,Wp1=Wp1W_1 = W'_1, \dots, W_{p-1} = W'_{p-1},则 WW 的字典序小于 WW'

输入格式

第一行包含两个整数 NNEE

接下来 EE 行,每行两个整数 AiA_iBiB_i,表示第 ii 条道路连接的两个交汇点。

最后一行包含 N1N - 1 个整数,表示你想保留的道路编号,构成的集合 RR

输出格式

输出 EE 个整数,表示字典序最小的排列 WW,第 ii 个数是第 ii 条道路的养护成本。

4 5
3 4
1 2
2 3
1 3
1 4
2 4 5
3 4 5 1 2
4 4
1 2
1 4
2 3
3 4
1 3 4
1 4 2 3

提示

【数据范围】

  • 1N,E3×1051 \leq N, E \leq 3 \times 10^5
  • 1AiBiN1 \leq A_i \neq B_i \leq N
  • 1RiE1 \leq R_i \leq E
  • 仅使用 RR 中的道路也能保证所有交汇点连通。
子任务编号 分值 额外限制
11 88 1N,E91 \leq N, E \leq 9
22 1919 1N,E1031 \leq N, E \leq 10^3
33 99 ARi=1, BRi=i+1A_{R_i} = 1,\ B_{R_i} = i + 1,即 RR 构成一棵星形树
44 1010 ARi=i, BRi=i+1A_{R_i} = i,\ B_{R_i} = i + 1,即 RR 构成一条链
55 E=N, Ai=i, Bi=imodN+1E = N,\ A_i = i,\ B_i = i \bmod N + 1
66 1212 E=NE = N
77 3232 无额外限制