hdu5739Fantasia(多校第二场1006) 割点+逆元
Fantasia
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
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 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.
3 2
1 2 3
1 2
2 3
#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;
}
最新文章
- hbase shell command
- CLR via C#(13)-浅谈事件
- int与string之间的类型转换--示例
- Apache CXF自定义拦截器
- 压缩js和css, IIS开启Etags, IIS开启Gzip
- Ubuntu could not write bytes broken pipe
- [ActionScript 3.0] Away3D 官网实例
- HDU4542 小明系列故事——未知剩余系
- 读取iis日志到sql server
- Azure 媒体服务支持 DASH 实时传送流
- 听同事讲 Bayesian statistics: Part 2 - Bayesian inference
- IDL 数组运算
- Clean http handlers in Go
- linux文件管理之查找
- 因为错误关闭Selinux导致CentOS7启动失败(进度条卡死,图形界面加载卡死)
- 在shell脚本中调用另一个脚本的三种不同方法(fork, exec, source)——转载
- 【机器学习】粗糙集(Rough Set Approach)
- 常见的mysql 进程state<;转自网络>;
- spring 事务配置
- WebAPI 实现前后端分离的示例