CodeForces 1389G Directing Edges 邊聯通分量縮點+樹形dp+rerooting technique

題目連結：https://codeforces.com/contest/1389/problem/G

G. Directing Edges

time limit per test

4 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

You are given an undirected connected graph consisting of nn vertices and mm edges. kk vertices of this graph are special.

You have to direct each edge of this graph or leave it undirected. If you leave the ii-th edge undirected, you pay wiwi 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 cici coins for each saturated vertex ii. Thus, your total profit can be calculated as ∑i∈Sci−∑j∈Uwj∑i∈Sci−∑j∈Uwj, where SS is the set of saturated vertices, and UU is the set of edges you leave undirected.

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

Input

The first line contains three integers nn, mm and kk (2≤n≤3⋅1052≤n≤3⋅105, n−1≤m≤min(3⋅105,n(n−1)2)n−1≤m≤min(3⋅105,n(n−1)2), 1≤k≤n1≤k≤n).

The second line contains kk pairwise distinct integers v1v1, v2v2, ..., vkvk (1≤vi≤n1≤vi≤n) — the indices of the special vertices.

The third line contains nn integers c1c1, c2c2, ..., cncn (0≤ci≤1090≤ci≤109).

The fourth line contains mm integers w1w1, w2w2, ..., wmwm (0≤wi≤1090≤wi≤109).

Then mm lines follow, the ii-th line contains two integers xixi and yiyi (1≤xi,yi≤n1≤xi,yi≤n, xi≠yixi≠yi) — the endpoints of the ii-th edge.

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

Output

Print nn integers, where the ii-th integer is the maximum profit you can get if you have to make the vertex ii saturated.

Examples

input

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

output

11 2 5 
      

input

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

output

21 21 21 21       

題意：n點m條邊的無向圖，k個特殊點。現在可以為每一條邊指定方向，也可以不指定方向，若不指定方向則會消耗Wi，反之不會有任何消耗。指定完方向後，若所有特殊點均可到達點i，則會獲得Ci的價值。這樣就會獲得一個總價值。對于點i，求出所有特殊點都可以到達點i的情況下的最大總價值。本題需要求出i為1至n的所有解。

題解：本題需要在O(n)的複雜度下解決問題。要在無向圖上解決該問題比較棘手。我們想辦法把圖上的問題轉換為樹上的問題，就有可能在O(n)的複雜度下解決問題。對于圖的每個邊聯通分量，一定存在一種方案定向所有邊以後，邊連通分量中的點兩兩可達。（學習下邊聯通分量的概念，很容易證明這點）。是以，我們可以首先通過Tarjan算法（O(n)），求出圖的所有邊聯通分量。由于，邊聯通分量可以定向所有邊以後，裡面的點依然兩兩可達，是以我們可以把邊聯通分量中的點縮（抽象）為一個點，這個點的權值為邊聯通分量中所有點的和。縮點以後，新的圖就是一顆樹，這樣問題就轉化為樹上的問題。

我們先考慮求一個點v的解，我們用動态規劃來解決這個問題。我們定義dp(v) 為：以點v為根節點的子樹，所有特殊點必達根節點v的情況下能得到的最大值。樹的根節點dp(v)的值，就是問題的解。我們來考慮下如何轉移，我們假設點v的兒子節點有SonV1，SonV2....。首先由于根節點v必達，是以dp(v)可以初始化為v的點權C(v)。對于每個兒子節點SonV，我們分類讨論如何轉移：

以SonV為根節點的子樹裡面沒有特殊點：對于這種情況我們定向點V指向點SonV，并且SonV為根的子樹的所有邊都定向為節點指向其兒子節點即可，這樣我們可以獲得這顆子樹的所有收益。dp(v)+=SumC(SonV)

以SonV為根節點的子樹裡面包含所有特殊點：這種情況我們定向點SonV指向點V即可。dp(v)+=dp(SonV)

除去上面兩種情況的其他情況：由于根節點v必達，而子樹裡面又包含特殊點，此時有兩種可能的邊定向方法，我們取最優的方案。一種是點SonV指向點V，這時獲得收益為0。另外一種是不定向這條邊，這時獲得的收益為dp(sonv)-W(邊權)。轉移為dp(v)+=max(0,dp(sonv)-W(邊權))

這樣我們就可以O(n)求出根節點V的解，但要求出所有點的解，現在的複雜度為O(n2)，我們還要想辦法。由于根節點的解才是我們要求解的問題的最優解。我們可以用rerooting technique解決這個問題。我們可以以DFS的順序，依次把每個點旋轉為根節點，當DFS通路到這個點的時候，這個點就是現在的樹的根節點，當這個點通路完畢以後，它的上一個點就又變為根節點。并在這個過程中維護dp(v)的值，對于我們可以O(1)維護每次dp值的變化，當點V為根節點，要把它的兒子點SonV旋轉為根節點，隻需要把V變為點SonV的兒子，重新計算V的dp值和SonV的dp值即可，它的dp值就是問題的解。這樣我們再通過一次O(n)的rerooting technique，就能求解出所有答案。

代碼如下:

#include<bits/stdc++.h>

using namespace std;
const int nn =310000;
const int inff = 0x3fffffff;
const double eps = 1e-8;
typedef long long LL;
const double pi = acos(-1.0);
int n,m,k;
int v[nn];
LL c[nn];
LL w[nn];
int x[nn],y[nn];
struct Edge
{
    int en,next;
    LL weight;
}E[nn*2];
int p[nn],num;
void addEdge(int st,int en,LL weight)
{
    E[num].en = en;
    E[num].weight = weight;
    E[num].next = p[st];
    p[st]=num++;
}
LL dfn[nn],minDfn[nn];
stack<int>sta;
bool vist[nn];
LL dfsCnt;
LL color[nn],colorCnt,colorC[nn];
//Tarjan求圖的邊聯通分量
void dfs(int st,int pre)
{
    dfn[st]=minDfn[st]=++dfsCnt;
    sta.push(st);
    vist[st] = true;
    for(int i=p[st];i!=-1;i=E[i].next)
    {
        int en = E[i].en;
        if(en==pre)
            continue;
        if(!vist[en])
            dfs(en,st);
        minDfn[st] = min(minDfn[st],minDfn[en]);
    }
    if(minDfn[st]==dfn[st])
    {
        ++colorCnt;
        while(true)
        {
            int id=sta.top();
            sta.pop();
            color[id] = colorCnt;
            if(id==st)
            {
                break;
            }
        }
    }
}
LL dp[nn];
LL sumC[nn],superN[nn];
LL colorSuper[nn];
//樹形dp
void TreeDp(int st,int pre)
{
    dp[st] = colorC[st];
    sumC[st] = colorC[st];
    superN[st] = colorSuper[st];
    for(int i=p[st];i!=-1;i=E[i].next)
    {
        int en = E[i].en;
        if(en==pre)
            continue;
        TreeDp(en,st);
        superN[st]+=superN[en];
        sumC[st]+=sumC[en];
        if(superN[en]==0)
        {
            dp[st]+=sumC[en];
        } else {
            if(superN[en]==k)
                dp[st]+=dp[en];
            else
                dp[st]+=max(LL(0),dp[en]-E[i].weight);
        }
    }
}
LL ans[nn];//每個點為根節點的dp值
//rerooting technique DFS求解每個點為根節點的解
void calcAns(int st,int pre,LL preWeight)
{
    if(pre==-1)
        ans[st]=dp[st];
    else
    {
        LL superNPre = superN[1]-superN[st];
        LL sumCPre = sumC[1]-sumC[st];
        LL dpPre;//父節點變為兒子節點時新的dp值
        if(superN[st]==0)
        {
            dpPre=ans[pre]-sumC[st];
        } else {
            if(superN[st]==superN[1])
                dpPre = ans[pre]-dp[st];
            else
                dpPre=ans[pre]-max(LL(0),dp[st]-preWeight);
        }
        if(superNPre==0)
            ans[st]=dp[st]+sumCPre;
        else {
            if(superNPre==superN[1])
                ans[st]=dp[st]+dpPre;
            else
                ans[st]=dp[st]+max(LL(0),dpPre-preWeight);
        }
    }
    for(int i=p[st];i!=-1;i=E[i].next)
    {
        int en = E[i].en;
        if(en==pre)
            continue;
        calcAns(en,st,E[i].weight);
    }
}
int main()
{
    memset(p,-1,sizeof(p));
    memset(vist,false,sizeof(vist));
    num = 0;
    colorCnt = 0;
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
        scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)
        scanf("%lld",&c[i]);
    for(int i=1;i<=m;i++)
        scanf("%lld",&w[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        addEdge(x[i],y[i],w[i]);
        addEdge(y[i],x[i],w[i]);
    }
    dfsCnt=0;
    //求邊聯通分量
    dfs(1,-1);
    memset(p,-1,sizeof(p));
    num = 0;
    //将邊聯通分量縮點，建新圖
    for(int i=1;i<=m;i++)
    {
        if(color[x[i]]!=color[y[i]])
        {
            addEdge(color[x[i]],color[y[i]],w[i]);
            addEdge(color[y[i]],color[x[i]],w[i]);
        }
    }
    memset(colorC,0,sizeof(colorC));
    for(int i=1;i<=n;i++)
    {
        colorC[color[i]]+=c[i];
    }
    memset(colorSuper,0,sizeof(colorSuper));
    for(int i=1;i<=k;i++)
    {
        colorSuper[color[v[i]]]++;
    }
    //樹形dp
    TreeDp(1,-1);
    /*for(int i=1;i<=n;i++)
        cout<<i<<" "<<color[i]<<" dp "<<dp[color[i]]<<endl;*/
    //求每個點的解
    calcAns(1,-1,0);
    for(int i=1;i<=n;i++)
    {
        cout<<ans[color[i]]<<" ";
    }
    return 0;
}