Fantasia
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description Professor Zhang has an undirected graph G with n vertices and m edges. Each vertex is attached with a weight wi. Let Gi be the graph after deleting the i-th vertex from graph G. Professor Zhang wants to find the weight of G1,G2,...,Gn.
The weight of a graph G is defined as follows:
1. If G is connected, then the weight of G is the product of the weight of each vertex in G.
2. Otherwise, the weight of G is the sum of the weight of all the connected components of G.
A connected component of an undirected graph G is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in G.
Input There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n and m (2≤n≤105,1≤m≤2×105) -- the number of vertices and the number of edges.
The second line contains n integers w1,w2,...,wn (1≤wi≤109), denoting the weight of each vertex.
In the next m lines, each contains two integers xi and yi (1≤xi,yi≤n,xi≠yi), denoting an undirected edge.
There are at most 1000 test cases and ∑n,∑m≤1.5×106.
Output For each test case, output an integer S=(∑i=1ni⋅zi) mod (109+7), where zi is the weight of Gi.
Sample Input 1 3 2 1 2 3 1 2 2 3
Sample Output 20 題目位址：http://acm.hdu.edu.cn/showproblem.php?pid=5739 題目描述： 有n個節點，每個節點有個值，然後m條邊構成可能不止一張張圖，每張圖的價值是每個節點的值的乘積，然後總的價值就是所有圖的價值加起來。 現在要分别删除每個點，G1就是代表的删除編号為1的節點，所有圖加起來的價值。 然後問你1*G[2] + 2*G[2] + ……+n*G[n]. 最後的值膜一個1e9+7。 題解： 這個題很顯然就是求割點，如果不是割點，就直接删除這個點就好了，如果是割點就複雜一點，就需要将該點的子樹中最多能夠通路到該點的子樹的值給處理出來。然後把子樹分開，另外處理就好了，還是看代碼分析吧。道理是這麼說，但是中途寫錯了好多東西TAT，對着資料改到現在...唉.... 代碼：
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
#include<set>
#include<string>
#include<map>
#define inf 9223372036854775807
#define INF 9e7+5
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const db eps = 1e-9;
ll va[maxn], w[maxn], Sum, ans[maxn];
int pre[maxn], dfs_tim, tot, n, m, low[maxn], t, vep[maxn];
bool vis[maxn];
vector<int> G[maxn];
void init() {
memset(vis, false, sizeof(vis));
memset(pre, 0, sizeof(pre));
Sum = tot = dfs_tim = 0;
for (int i = 1; i <= n; i++) G[i].clear();
}
//快速幂，求逆元用
ll pow_mod(ll a, ll b, ll p) {
ll ret = 1;
while(b) {
if(b & 1) ret = (ret * a) % p;
a = (a * a) % p;
b >>= 1;
}
return ret;
}
//費馬小定理求的逆元
ll inv(ll x) {
return pow_mod(x, mod-2, mod);
}
// 先寫好，懶得每次模
void add(ll &x, ll y) {
x = x + y;
x = (x + mod) % mod;
}
// 主要是把每張圖的價值處理出來
void Find(int x) {
va[x] = w[x];
for (int i = 0; i < G[x].size(); i++) {
int u = G[x][i];
if (vis[u]) continue;
vis[u] = true; Find(u);
va[x] = va[x] * va[u] % mod;
}
}
ll dfs(int x, int fa, int root) { //目前節點，父節點和根節點
low[x] = pre[x] = ++dfs_tim; //pre數組記錄通路的時間
ans[x] = inv(w[x]); //删除此時通路的節點
int cld = 0; ll sum = 0, res = w[x], pro = 1;
for (int i = 0; i < G[x].size(); i++) {
int u = G[x][i];
if (!pre[u]) {
cld++;
ll tmp = dfs(u, x, root); //tmp傳回的是對于u這顆子樹的價值
low[x] = min(low[x], low[u]); //更新x節點所能通路的最早的祖先
if (low[u] >= pre[x]) { //如果u這顆子樹所能通路的是x，那麼說明x節點被删除，u這顆子樹會被分開
add(sum, tmp); //sum表示的是x節點被删除後，x會被分開的子樹的價值之和
ans[x] = ans[x] * inv(tmp) % mod; //和上面删除節點一樣，表示将這顆子樹删除
}
res = res * tmp % mod; //求子樹的價值
}
else if (u != fa) low[x] = min(low[x], pre[u]); //對于通路比目前節點早的節點，更新能通路的最早節點
} //tt表示的是除了這幅圖，其它圖的價值之和
ll tt = (Sum - va[root] + mod) % mod; //va[roor]*ans[x]中ans[x]已經是逆元了,是以這句話
ans[x] = va[root] * ans[x] % mod; //表示的是将x節點和會分開的子樹 删除後該圖的值
if (fa == -1 && ans[x] == 1) ans[x] = 0; //對于一張圖，如果他的子節點全部被删除了，我們
//求到的ans[x]是1，但事實上應 該是0，是以
//需要特判一下，比如這樣一張圖 1 - 2， 1 - 3.
add(ans[x], tt); add(ans[x], sum); //将其他圖和删除的子樹加起來
if (fa == -1) {
if (cld == 1) { //對于最開始的祖先，如果他隻有一個兒
//子，那麼他不是割點，學割點應該都學過QAQ
ans[x] = va[root] * inv(w[x]) % mod;
add(ans[x], tt);
}
else if (G[x].size() == 0) {
ans[x] = tt; //如果這是一個孤立點，删除後就直接是其他圖的值
}
}
return res;
}
void solve() {
cin >> n >> m;
init();
for (int i = 1; i <= n; i++) scanf("%I64d", &w[i]);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
vis[i] = true;
vep[++tot] = i; Find(i); //vep數組用來存每次要通路的圖的開始節點
add(Sum, va[i]); //所有圖的總價值,va[i]就代表了這張圖的總價值
}
for (int i = 1; i <= tot; i++) {
dfs(vep[i], -1, vep[i]); //-1位置代表的父節點，對于最開始的點的父親設為-1
}
ll pri = 0;
for (ll i = 1; i <= n; i++) {
add(pri, i*ans[i]%mod); //求出最後的值
}
cout << pri << endl;
}
int main() {
//cin.sync_with_stdio(false);
// freopen("tt.txt", "r", stdin);
//freopen("hh.txt", "w", stdout);
cin >> t;
while (t--)
solve();
return 0;
}