Directing Edges
Contest: Educational Codeforces Round 92 (Rated for Div. 2)
Difficulty rating: 2800
Tags: dfs and similar, dp, graphs, trees

You are given an undirected connected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. $$$k$$$ vertices of this graph are special.

You have to direct each edge of this graph or leave it undirected. If you leave the $$$i$$$-th edge undirected, you pay $$$w_i$$$ coins, and if you direct it, you don't have to pay for it.

Let's call a vertex saturated if it is reachable from each special vertex along the edges of the graph (if an edge is undirected, it can be traversed in both directions). After you direct the edges of the graph (possibly leaving some of them undirected), you receive $$$c_i$$$ coins for each saturated vertex $$$i$$$. Thus, your total profit can be calculated as $$$\sum \limits_{i \in S} c_i - \sum \limits_{j \in U} w_j$$$, where $$$S$$$ is the set of saturated vertices, and $$$U$$$ is the set of edges you leave undirected.

For each vertex $$$i$$$, calculate the maximum possible profit you can get if you have to make the vertex $$$i$$$ saturated.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$ and $$$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$$$).

The second line contains $$$k$$$ pairwise distinct integers $$$v_1$$$, $$$v_2$$$, ..., $$$v_k$$$ ($$$1 \le v_i \le n$$$) — the indices of the special vertices.

The third line contains $$$n$$$ integers $$$c_1$$$, $$$c_2$$$, ..., $$$c_n$$$ ($$$0 \le c_i \le 10^9$$$).

The fourth line contains $$$m$$$ integers $$$w_1$$$, $$$w_2$$$, ..., $$$w_m$$$ ($$$0 \le w_i \le 10^9$$$).

Then $$$m$$$ lines follow, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$) — the endpoints of the $$$i$$$-th edge.

There is at most one edge between each pair of vertices.

Output format:
Print $$$n$$$ integers, where the $$$i$$$-th integer is the maximum profit you can get if you have to make the vertex $$$i$$$ saturated.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
Consider the first example:

- the best way to make vertex $$$1$$$ saturated is to direct the edges as $$$2 \to 1$$$, $$$3 \to 2$$$; $$$1$$$ is the only saturated vertex, so the answer is $$$11$$$;
- the best way to make vertex $$$2$$$ saturated is to leave the edge $$$1-2$$$ undirected and direct the other edge as $$$3 \to 2$$$; $$$1$$$ and $$$2$$$ are the saturated vertices, and the cost to leave the edge $$$1-2$$$ undirected is $$$10$$$, so the answer is $$$2$$$;
- the best way to make vertex $$$3$$$ saturated is to direct the edges as $$$2 \to 3$$$, $$$1 \to 2$$$; $$$3$$$ is the only saturated vertex, so the answer is $$$5$$$.

The best course of action in the second example is to direct the edges along the cycle: $$$1 \to 2$$$, $$$2 \to 3$$$, $$$3 \to 4$$$ and $$$4 \to 1$$$. That way, all vertices are saturated.

Example input:
3 2 2
1 3
11 1 5
10 10
1 2
2 3

Example output:
11 2 5

Example input:
4 4 4
1 2 3 4
1 5 7 8
100 100 100 100
1 2
2 3
3 4
1 4

Example output:
21 21 21 21

Editorial:
Suppose we want to calculate the maximum profit for some vertex in $$$O(n)$$$. Let's try to find out how it can be done, and then optimize this process so we don't have to run it $$$n$$$ times.
First of all, we have to find the bridges and biconnected components in our graph. Why do we need them? Edges in each biconnected component can be directed in such a way that it becomes a strongly connected component, so we don't have to leave these edges undirected (it is never optimal). Furthermore, for each such component, either all vertices are saturated or no vertex is saturated. Let's build a tree where each vertex represents a biconnected component of the original graph, and each edge represents a bridge. We can solve the problem for this tree, and then the answer for some vertex of the original graph is equal to the answer for the biconnected component this vertex belongs to.
Okay, now we have a problem on tree. Let's implement the following dynamic programming solution: root the tree at the vertex we want to find the answer for, and for each vertex, calculate the value of $$$dp_v$$$ — the maximum profit we can get for the subtree of vertex $$$v$$$, if it should be reachable by all special vertices from its subtree.
Let's analyze how we can calculate these $$$dp$$$ values. Suppose we have a vertex $$$v$$$ with children $$$v_1$$$, $$$v_2$$$, ..., $$$v_d$$$, we have already calculated the $$$dp$$$ values for the children, and we want to calculate $$$dp_v$$$. First of all, since the vertex $$$v$$$ is going to be saturated, we will get the profit from it, so we initialize $$$dp_v$$$ with $$$c_v$$$. Then we should decide whether we want to get the profit from the children of vertex $$$v$$$. Suppose the edge leading from $$$v$$$ to $$$v_i$$$ has weight $$$w_i$$$. If we want to take the profit from the subtree of $$$v_i$$$, we (usually) have to make this edge undirected, so both vertices are saturated, thus we get $$$dp_{v_i} - w_i$$$ as profit — or we could leave this edge directed from $$$v_i$$$ to $$$v$$$, so the vertex $$$v$$$ is saturated, and $$$v_i$$$ is not, and get $$$0$$$ as the profit. But sometimes we can gain the profit from the vertex $$$v_i$$$ and its subtree without leaving the edge undirected: if all special vertices belong to the subtree of $$$v_i$$$, we can just direct this edge from $$$v_i$$$ to $$$v$$$, and there is no reason to choose the opposite direction or leave the edge undirected. Similarly, if all special vertices are outside of this subtree, there's no reason to direct the edge from $$$v_i$$$ to $$$v$$$. So, if one of this conditions is met, we can get the full profit from the subtree of $$$v_i$$$ without leaving the edge undirected.
Okay, let's summarize it. We can calculate $$$dp_v$$$ as $$$dp_v = c_v + \sum \limits_{i=1}^{d} f(v_i)$$$, where $$$f(v_i)$$$ is either $$$dp_{v_i}$$$ if one of the aforementioned conditions is met (we don't have to leave the edge undirected if we want to saturate both vertices), or $$$f(v_i) = \max(0, dp_{v_i} - w_i)$$$ otherwise. Now we have an $$$O(n^2)$$$ solution.
Let's optimize it to $$$O(n)$$$. Root the tree at vertex $$$1$$$ and calculate the dynamic programming as if $$$1$$$ is the root. Then, we shall use rerooting technique to recalculate the dynamic programming for all other vertices: we will try each vertex as the root of the tree, and $$$dp_v$$$ is the answer for the vertex $$$v$$$ if it is the root. The rerooting technique works as follows: let's run DFS from the initial root of the tree, and when we traverse an edge by starting or finishing a recursive call of DFS, we move the root along the edge; so, if we call $$$DFS(x)$$$, $$$x$$$ is the current root; if it has some child $$$y$$$, we move the root to $$$y$$$ the same moment when we call $$$DFS(y)$$$, and when the call of $$$DFS(y)$$$ ends, the root moves back to $$$x$$$.
Okay, the only thing that's left is to describe how we move the root. If the current root is $$$x$$$, and we want to move it to $$$y$$$ (a vertex adjacent to $$$x$$$), then we have to change only the values of $$$dp_x$$$ and $$$dp_y$$$: first of all, since $$$y$$$ is no longer a child of $$$x$$$, we have to subtract the value that was added to $$$dp_x$$$ while we considered vertex $$$y$$$; then, we have to make $$$x$$$ the child of vertex $$$y$$$, so we add the profit we can get from the vertex $$$x$$$ to $$$dp_y$$$. It can be done in $$$O(1)$$$, so our solution runs in $$$O(n)$$$, though with a very heavy constant factor.