给出一张 $n$ 个点 $m$ 条边的无向图，有$k$ 个关键点。需要给所有无向边定向，如果第 $i$ 条边保留双向，要花费$w_i$的代价。我们称定向后的图上一个点是饱和的，当且仅当所有关键点都能到达它。此时这个点能够有 $c_i$
的收益。请对于每个$i = 1, 2, \ldots, n$ 回答，强制选择 $i$ 号点为饱和点时，收益减代价的最大值。

$n, m \le 3 \times 10 ^ 5$

如果出现了$双连通分量$，那么就可定向成强连通分量，就一定可以两两互通，就不需要考虑。

全部缩点之后，就变成了树。

考虑树上如果进行，并且显然这是个换根$dp$。

$dp[x]$表示以 $x$ 为根节点的子树里，保证 $x$ 是饱和的情况下最小的代价。

$dp[x]= \begin{cases} \sum dp[to]子树无关建点\\ \sum max(0,dp[to]-w)子树有关建点\\ \end{cases}$

换根$dp$

$dp[to]= \begin{cases} \sum dp[x]子树无关建点\\ \sum max(0,(dp[x]-max(0,dp[to]-w))-w)子树有关建点\\ \end{cases}$

代码

```c++

include

using namespace std;
typedef long long ll;

define pii pair

define mk make_pair

const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < ‘0’ || c > ‘9’)
{
if (c == ‘-‘)
f = -1;
c = getchar();
}
while (c >= ‘0’ && c <= ‘9’)
x = (x << 1) + (x << 3) + c - ‘0’, c = getchar();
return x * f;
}

ll sp[N], c[N], w[N], flag[N];

namespace tarjan
{
vector g[N];
int dfn[N], low[N], gcnt, ln, fa[N];
stack s;

void tarjan(int x, int f)
{
    dfn[x] = low[x] = ++gcnt;

    s.push(x);

    for (int i = 0; i < g[x].size(); i++)
    {
        int to = g[x][i];
        if (f == to)
            continue;
        if (!dfn[to])
        {
            tarjan(to, x);
            low[x] = min(low[x], low[to]);
        }
        else
            low[x] = min(low[x], dfn[to]);
    }

    if (dfn[x] == low[x])
    {

        ++ln;
        while (1)
        {
            int cur = s.top();
            s.pop();
            fa[cur] = ln;
            w[ln] += c[cur];
            flag[ln] |= sp[cur];
            if (cur == x)
                break;
        }
    }
}

} // namespace tarjan

struct Edge
{
int u, v;
int w;
} e[N];

vector g[N];

ll dp[N];

void dfs1(int x, int fa)
{
for (pii now : g[x])
{
int to = now.first;
if (fa == to)
continue;
dfs1(to, x);
flag[x] |= flag[to];
}
}
void dfs2(int x, int fa)
{
dp[x] = w[x];
for (pii now : g[x])
{
int to = now.first;
if (fa == to)
continue;
dfs2(to, x);
if (flag[to] == 0)
dp[x] += dp[to];
else if (dp[to] - now.second > 0)
dp[x] += dp[to] - now.second;
}
}

void dfs3(int x, int fa)
{

for (pii now : g[x])
{
    int to = now.first, w = now.second;
    if (fa == to)
        continue;
    if (flag[to] == 1)
        dp[to] += max(0ll, dp[x] - max(0ll, dp[to] - w) - w);
    else
        dp[to] = dp[x];
    dfs3(to, x);
}

}
int main()

{
int n = read(), m = read(), k = read();
for (int i = 1; i <= k; i++)
{
int x = read();
sp[x] = 1;
}
for (int i = 1; i <= n; i++)
c[i] = read();
for (int i = 1; i <= m; i++)
e[i].w = read();
for (int i = 1; i <= m; i++)
{
e[i].u = read(), e[i].v = read();
tarjan::g[e[i].u].push_back(e[i].v);
tarjan::g[e[i].v].push_back(e[i].u);
}
tarjan::tarjan(1, 0);

for (int i = 1; i <= m; i++)
{
    int u = tarjan::fa[e[i].u], v = tarjan::fa[e[i].v], w = e[i].w;
    if (u != v)
    {
        g[u].push_back(mk(v, w));
        g[v].push_back(mk(u, w));
    }
}
int rt = 1;
for (int i = 1; i <= tarjan::ln; i++)
    if (flag[i])
        rt = i;
dfs1(rt, 0);
dfs2(rt, 0);
dfs3(rt, 0);
for (int i = 1; i <= n; i++)
    printf("%lld ", dp[tarjan::fa[i]]);

}