题意：给一个无向图n个点1~n，m条边，sigma(i*zi)%(1e9+7)。zi是这个图删掉i点之后的价值。一个图的价值是所有连通子图的价值之和，连通图的价值是每个点的乘积。
题解：讲道理这题不算难。注意一点就是一开始给的图不一定是连通的。然后就是割点会把一个连通图分成两个连通图，而其他点不影响图的连通性。至于割点直接tarjan就可以了。
而且dfs的过程中也可以处理出答案。这题只需要把每个连通子图求出而不需要处理出强连通分量，所以省去了tarjan算法中的stack数组。
变量比较多，写起来很烦。。
AC代码（1934MS）：
#include <stdio.h> #include <string.h> #include <iostream> #include <vector> #include <math.h> using namespace std; typedef long long ll; const int N = 200010; const ll mod = 1e9+7; int n, m; // 同题目描述 int a[N]; // 记录每个点的权值 struct Edge // 前向星存边 { int to, next; } edge[N*4]; int cnt_edge; int head[N]; void add_edge(int u, int v) { edge[cnt_edge].to = v; edge[cnt_edge].next = head[u]; head[u] = cnt_edge++; } int dfn[N], low[N], idx; // tarjan中用到的变量 ll mul; // 临时变量，记录每个图的所有点乘积 ll ans[N]; // 对于每个割点 如果分割了这个点 这棵树的答案 ll smul[N]; // 对于每个割点 分割它后所有分出来的子树的乘积 bool cut[N]; // 割点 int graph_cnt; // 连通图数量 vector<int> G[N]; // 记录每个连通图 ll graph[N]; // 每个连通图所有点的乘积 int kind[N]; // 每个点属于哪个连通图 void init(int n) { for (int i = 0; i <= n; ++i) { head[i] = -1; dfn[i] = 0; ans[i] = 0; smul[i] = 1; cut[i] = false; G[i].clear(); } cnt_edge = 0; idx = 0; graph_cnt = 0; } ll pow_mod(ll x, ll n) { ll ans = 1; while (n) { if (n & 1) ans = ans * x % mod; x = x * x % mod; n >>= 1; } return ans; } void tarjan(int u, int fa) { dfn[u] = low[u] = ++idx; int child = 0; G[graph_cnt].push_back(u); kind[u] = graph_cnt; mul = mul * a[u] % mod; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == fa) continue; if (!dfn[v]) { ll tmp = mul; tarjan(v, u); low[u] = min(low[u], low[v]); if (low[v] >= dfn[u]) { // u是割点 ++child; ll inv = pow_mod(tmp, mod-2); tmp = mul * inv % mod; // mul/tmp 就是这个子图的乘积 ans[u] = (ans[u] + tmp) % mod; smul[u] = smul[u] * tmp % mod; } } else { low[u] = min(low[u], dfn[v]); } } if ((fa == -1 && child > 1) || (fa != -1 && child)) cut[u] = true; // u是割点 } int main(int argc, char const *argv[]) { //freopen("in", "r", stdin); int T; cin >> T; while (T--) { scanf("%d%d", &n, &m);init(n); for (int i = 1; i <= n; ++i) scanf("%d", a+i); int u, v; while (m--) { scanf("%d%d", &u, &v); add_edge(u, v); add_edge(v, u); } ll res = 0; for (int i = 1; i <= n; ++i) { if (!dfn[i]) { mul = 1; tarjan(i, -1); graph[graph_cnt] = mul; res = (res + mul) % mod; for (unsigned j = 0; j < G[graph_cnt].size(); ++j) { u = G[graph_cnt][j]; if (u != i) { ans[u] = (ans[u] + mul * pow_mod(smul[u]*a[u]%mod, mod - 2) % mod) % mod; //mul/smul[j]; } } ++graph_cnt; } } ll rut = 0; for (int i = 1; i <= n; ++i) { ll tmp; if (cut[i]) { // 如果是割点的话 就是这个点所在图分成多个子图 tmp = (res - graph[ kind[i] ] + ans[i] + mod) % mod; } else { if (G[kind[i]].size() == 1) { tmp = (res - a[i] + mod) % mod; } else { tmp = (res - graph[kind[i]] + graph[kind[i]] * pow_mod(a[i], mod-2) % mod + mod) % mod; } } rut = (rut + i * tmp % mod) % mod; } cout << rut << endl; } return 0; }