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>
using namespace std;
#pragma GCC optimize ("Ofast")
#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;
const ll maxn = 2e5 + 17 , md = 1e9 + 7 , inf = 2e16;
ll n , m , ans;
bitset<maxn> mark;
vector<ll> adj[maxn] , cc[maxn] , st , del , v;
vector<pll> cdj[maxn];
ll c[maxn] , o , dp[maxn] , ps[maxn] , pz[maxn];
void cDFS(ll r , ll par){
st.push_back(r);
mark[r] = true;
for(auto i : adj[r]){
if(i == par) continue;
if(mark[i]){
if(c[r] != -1) continue;
while(st.back() != i){
c[st.back()] = o;
cc[o].push_back(st.back());
del.push_back(st.back());
st.pop_back();
}
c[i] = o;
cc[o].push_back(i);
o++;
while(!del.empty()){
st.push_back(del.back());
del.pop_back();
}
continue;
}
cDFS(i , r);
}
st.pop_back();
return;
}
ll cal(ll l , ll r){
if(l >= r) return 0;
if(r - l == 1) return v[l];
ll m = (r + l) >> 1;
ll a = 1 , b = 1 , h = 1;
for(ll i = m - 1 ; i >= l ; i--){
h *= v[i]; h %= md;
a += h;
}
h = 1;
for(ll i = m + 1 ; i < r ; i++){
h *= v[i]; h %= md;
b += h;
}
a %= md; b %= md;
ll res = cal(l , m) + cal(m + 1 , r) + a * b % md * v[m];
return res % md;
}
void dDFS(ll r , ll t , ll par , bool f = false){
// cout<<r<<' '<<t<<' '<<par<<' '<<f<<endl;
if(r < n){
ll h = 1;
for(auto p : cdj[r]){
ll i = p.first , u = p.second;
if(i == par) continue;
dDFS(i , u , r);
h *= dp[i] + 1; h %= md;
}
dp[r] = h;
ans += h;
return;
}
swap(r , t);
if(f){
ll h = 1;
for(auto i : adj[r]){
ll u = (c[i] == -1 ? i : c[i]);
if(u == t) continue;
dDFS(u , i , t);
h *= dp[u] + 1; h %= md;
}
dp[r] = h;
return;
}
ll ind = -1 , sz = sze(cc[t]);
for(ll i = 0 ; i < sz ; i++){
if(cc[t][i] == r){
ind = i;
break;
}
}
v.clear();
for(ll i = ind + 1 ; i < sz ; i++){
dDFS(t , cc[t][i] , par , true);
v.push_back(dp[cc[t][i]]);
}
for(ll i = 0 ; i < ind ; i++){
dDFS(t , cc[t][i] , par , true);
v.push_back(dp[cc[t][i]]);
}
ll vs = sz - 1;
ps[0] = v[0] + 1;
pz[0] = v[0];
for(ll i = 1 ; i < vs ; i++){
pz[i] = pz[i - 1] * v[i] % md;
ps[i] = ps[i - 1] + pz[i]; ps[i] -= (ps[i] >= md) * md;
}
ll cur = 1 , res = 0;
for(ll i = vs - 1 ; i > 0 ; i--){
ll h = cur * ps[i - 1] % md;
res += h;
cur *= v[i]; cur %= md;
}
res += cur;
dp[t] = res % md;
ans += dp[t];
ans += cal(0 , vs);
return;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
memset(c , -1 , sizeof(c));
cin>>n>>m; o = n;
for(ll i = 0 ; i < m ; i++){
ll v , u;
cin>>v>>u; v--; u--;
adj[v].push_back(u); adj[u].push_back(v);
}
cDFS(0 , -1);
for(ll i = 0 ; i < n ; i++){
ll v = (c[i] == -1 ? i : c[i]);
for(auto j : adj[i]){
ll u = (c[j] == -1 ? j : c[j]);
if(v == u) continue;
cdj[v].push_back({u , j});
}
}
dDFS((c[0] == -1 ? 0 : c[0]) , 0 , -1);
ans %= md;
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... |