题目链接：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];elsedp[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];elsedpPre=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;elseans[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]]]++;}//树形dpTreeDp(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;
}