rockdu
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.
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.
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
Author
zimpha
Source
Recommend
大概题意：题目大概说给一张无向点带有权无向图。定义连通图的权值为图中各点权的乘积，图的权值为其包含的各连通图的权和。设zizi为删除i点后图的权值，求S=(∑_{i=1~n}i⋅zi) mod (1e9+7)S=(∑i=1ni⋅zi) mod (109+7)。
这就是点双树(圆方树)模板题了，大家可以看这篇博客，写的真的很好。基本上一看就会，并且代码实现也很有借鉴意义，用了以边代点的思想。这篇博客
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<stack>
#define LL long long
using namespace std;
int n, m;
const int maxn = 4e5 + 5, mod = 1e9 + 7;
struct edge {
int v, next, vis;
}e[maxn << 4];
int TH[maxn << 1], head[maxn], cnt;
void adde(int * H, const int &u, const int &v) {
e[++cnt] = (edge) {v, H[u], 0}, H[u] = cnt;
}
inline int OPT(int x) {return ((x - 1) ^ 1) + 1;}
stack<int > stk;
int u, v, dfn[maxn], low[maxn], w[maxn << 1], dcnt;
int nd[maxn], icnt, rt[maxn], vis[maxn];
int Tarjan(int u) {
int v;
low[u] = dfn[u] = ++dcnt;
for(register int i = head[u]; i; i = e[i].next) {
v = e[i].v;
if(e[i].vis) continue;
e[OPT(i)].vis = e[i].vis = 1, stk.push(i);
if(dfn[v]) {
low[u] = min(low[u], dfn[v]);
continue;
}
low[u] = min(low[u], Tarjan(v));
if(low[v] >= dfn[u]) {
int v, id = ++icnt;
w[id] = 1;
do {
v = stk.top(), stk.pop();
nd[v] = nd[OPT(v)] = id;
adde(TH, nd[v], e[v].v);
adde(TH, e[v].v, nd[v]);
adde(TH, nd[v], e[OPT(v)].v);
adde(TH, e[OPT(v)].v, nd[v]);
//cerr << nd[v] << "---" << e[v].v << endl;
//cerr << nd[v] << "---" << e[OPT(v)].v << endl;
} while(e[OPT(v)].v != u);
}
}
return low[u];
}
LL inv(LL a, int b = mod - 2) {
LL ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod, b >>= 1;
}
return ans;
}
LL mul[maxn], sub[maxn], in[maxn], val, ans;
void dfs(int u, int rt) {
int deg = 0;
vis[u] = 1, mul[u] = w[u], sub[u] = 0, in[u] = rt;
for(register int i = TH[u]; i; i = e[i].next) {
int v = e[i].v;
if(vis[v]) continue;
dfs(v, rt), mul[u] = (mul[v] * mul[u]) % mod;
sub[u] = (sub[u] + mul[v]) % mod;
}
}
int t;
int main() {
scanf("%d", &t);
while(t--) {
memset(TH, 0, sizeof(TH));
memset(head, 0, sizeof(head));
rt[0] = dcnt = icnt = cnt = 0;
memset(dfn, 0, sizeof(dfn));
memset(vis, 0, sizeof(vis));
memset(low, 0, sizeof(low));
ans = val = 0;
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; ++i) scanf("%d", &w[i]);
for(register int i = 1; i <= m; ++i)
scanf("%d%d", &u, &v), adde(head, u, v), adde(head, v, u);
icnt = n;
for(register int i = 1; i <= n; ++i)
if(!dfn[i]) Tarjan(i), rt[++rt[0]] = i;
for(register int i = 1; i <= rt[0]; ++i)
dfs(rt[i], rt[i]), val = (val + mul[rt[i]]) % mod;
for(register int i = 1; i <= n; ++i) {
ans = (ans + (((val - mul[in[i]]) % mod + sub[i]) % mod) * i % mod) % mod;
if(i != in[i]) ans = (ans + (mul[in[i]] * inv(mul[i]) % mod) * i % mod) % mod;
}
printf("%lld\n", (ans + mod) % mod);
}
return 0;
}
没有帐号? 立即注册