This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define pb push_back
#define ff first
#define ss second
void dbg(){
cerr << endl;
}
template<typename Head, typename... Tail> void dbg(Head h, Tail... t){
cerr << " " << h << ",";
dbg(t...);
}
#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">:", dbg(__VA_ARGS__)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void IOS(){
cin.tie(0) -> sync_with_stdio(0);
// #ifndef ONLINE_JUDGE
// freopen("inp.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// #endif
}
const ll mod = 1e9 + 7, maxn = 1e5 + 5, lg = 19, inf = ll(1e9) + 5;
vector<int> adj[maxn], adj2[maxn], lis[maxn];
bool vis[maxn], king[maxn];
int cnt_cycle, grp[maxn];
pp dfs(int r, int p){
pp res = {-1, -1};
vis[r] = true;
for(int c: adj[r]) if(c - p){
if(vis[c]){
if(res.ff + 1) continue;
res = {c, cnt_cycle++};
grp[r] = res.ss;
}else{
pp ret = dfs(c, r);
if(ret.ff + 1){
assert(res.ff == -1);
grp[r] = ret.ss;
res = ret;
king[r] = ret.ff == r;
}
}
}
if(res.ff == r) res = {-1, -1};
return res;
}
ll slv(vector<ll> a){
if(sz(a) < 3) return a[0];
int n = sz(a);
vector<ll> suf(n + 1);
suf[n] = 1;
per(i,n-1,0){
suf[i] = suf[i+1]*a[i]%mod;
}
ll cr = 0, mul = a[0];
rep(i,2,n+1) cr += suf[i], cr %= mod;
ll res = 0;
rep(i,0,n-1){
res = (res + cr*mul)%mod;
cr = (cr - suf[i + 2] + mod)%mod;
mul = mul*a[i + 1]%mod;
}
return res;
}
ll slv2(vector<ll> a){
ll res = 0;
ll cr = 0;
rep(i,0,sz(a)){
cr = (cr + 1)*a[i]%mod;
res = (res + cr)%mod;
}
return res;
}
ll dp[maxn], dp2[maxn], ans;
void dfs2(int r, int p){
for(int c: adj2[r]){
if(c - p){
dfs2(c, r);
}
}
int pos = 0, ptr = 0;
for(int u: lis[r]){
dp2[u] = 1;
for(int c: adj[u]) if(grp[u] - grp[c] && grp[c] - p){
dp2[u] = dp2[u]*(dp[c] + 1)%mod;
}
if(king[u]) pos = ptr;
ptr++;
}
vector<ll> tmp, tmp2;
rep(i,pos,sz(lis[r])) tmp.pb(dp2[lis[r][i]]);
rep(i,0,pos) tmp.pb(dp2[lis[r][i]]);
rep(i,pos+1,sz(lis[r])) dp[lis[r][i]] = dp2[lis[r][i]], tmp2.pb(dp[lis[r][i]]);
rep(i,0,pos) dp[lis[r][i]] = dp2[lis[r][i]], tmp2.pb(dp[lis[r][i]]);
dp[lis[r][pos]] = slv(tmp);
ans = (ans + dp[lis[r][pos]] + slv2(tmp2))%mod;
}
int main(){ IOS();
int n, m; cin >> n >> m;
rep(i,0,m){
int u, v; cin >> u >> v; u--, v--;
adj[u].pb(v), adj[v].pb(u);
}
fill(grp, grp + n, -1);
dfs(0, -1);
rep(i,0,n){
if(grp[i] == -1) grp[i] = cnt_cycle++;
lis[grp[i]].pb(i);
}
rep(i,0,n){
for(int c: adj[i]){
if(grp[i] - grp[c]){
adj2[grp[i]].pb(grp[c]);
}
}
}
dfs2(0, -1);
// rep(i,0,n){
// er(i+1, dp[i], dp2[i], king[i], grp[i]);
// }
// er(slv2({1, 2, 3, 4}));
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |