← 返回题目列表

Codeforces · 1389/G

G. 定向边缘

中文机器翻译题面 查看原题

给你一个无向连通图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。该图的 $$$k$$$ 顶点是特殊的。

您必须定向该图的每条边或使其保持无向。如果你让第 $$$i$$$ 条边不定向,你需要支付 $$$w_i$$$ 硬币,如果你定向它,你就不必支付费用。

如果一个顶点可以沿着图的边从每个特殊顶点到达(如果边是无向的,则可以在两个方向上遍历它),我们称该顶点为饱和顶点。在您定向图的边(可能其中一些边是无向的)后,您会为每个饱和顶点 $$$i$$$ 收到 $$$c_i$$$ 硬币。因此,您的总利润可以计算为 $$$\sum \limits_{i \in S} c_i - \sum \limits_{j \in U} w_j$$$,其中 $$$S$$$ 是饱和顶点集,而 $$$U$$$ 是无向边集。

对于每个顶点 $$$i$$$,计算如果必须使顶点 $$$i$$$ 饱和的话可以获得的最大可能利润。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$n - 1 \le m \le \min(3 \cdot 10^5, \frac{n(n-1)}{2})$$$, $$$1 \le k \le n$$$)。

第二行包含 $$$k$$$ 成对不同的整数 $$$v_1$$$, $$$v_2$$$, ..., $$$v_k$$$ ($$$1 \le v_i \le n$$$) — 特殊顶点的索引。

第三行包含 $$$n$$$ 整数 $$$c_1$$$, $$$c_2$$$, ..., $$$c_n$$$ ($$$0 \le c_i \le 10^9$$$)。

第四行包含 $$$m$$$ 整数 $$$w_1$$$, $$$w_2$$$, ..., $$$w_m$$$ ($$$0 \le w_i \le 10^9$$$)。

接下来是 $$$m$$$ 行,第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$) — 第 $$$i$$$ 条边的端点。

每对顶点之间最多有一条边。

输出

打印 $$$n$$$ 个整数,其中第 $$$i$$$ 个整数是如果必须使顶点 $$$i$$$ 饱和时可以获得的最大利润。

示例

输入 #1

3 2 2
1 3
11 1 5
10 10
1 2
2 3

输出 #1

11 2 5

输入 #2

4 4 4
1 2 3 4
1 5 7 8
100 100 100 100
1 2
2 3
3 4
1 4

输出 #2

21 21 21 21

注意

考虑第一个例子:

- 使顶点 $$$1$$$ 饱和的最佳方法是将边定向为 $$$2 \to 1$$$, $$$3 \to 2$$$; $$$1$$$ 是唯一饱和的顶点,所以答案是 $$$11$$$;
- 使顶点 $$$2$$$ 饱和的最佳方法是让边 $$$1-2$$$ 无向,并将另一条边定向为 $$$3 \to 2$$$; $$$1$$$和$$$2$$$是饱和顶点,离开边$$$1-2$$$无向的成本是$$$10$$$,所以答案是$$$2$$$;
- 使顶点 $$$3$$$ 饱和的最佳方法是将边定向为 $$$2 \to 3$$$, $$$1 \to 2$$$; $$$3$$$ 是唯一饱和的顶点,因此答案是 $$$5$$$。

第二个示例中的最佳操作方案是沿循环引导边:$$$1 \to 2$$$、$$$2 \to 3$$$、$$$3 \to 4$$$ 和 $$$4 \to 1$$$。这样,所有顶点都饱和了。