Submission #1259118

#TimeUsernameProblemLanguageResultExecution timeMemory
1259118mohammadsamSubtree (INOI20_subtree)C++20
100 / 100
125 ms36280 KiB
/* in the name of god */ //#pragma GCC optimize("Ofast,O3,unroll-loops") //#pragma GCC target("avx,avx2,fma") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native") #include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int> pii; typedef pair<long long ,long long> pll; typedef long long ll ; #define File freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #define all(V) V.begin(),V.end() #define setprec(x) fixed << setprecision(x) #define Mp(a,b) make_pair(a,b) #define len(V) (int)(V.size()) #define sep ' ' #define endl '\n' #define pb(x) push_back(x) #define fi first #define sec second #define popcount(x) __builtin_popcount(x) #define lid u<<1 #define rid (lid)|1 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll N = 2e5 + 10,SQ=320,LOG=31; const ll inf = 2e9 , MD = 1e9 + 7; inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);} int n , m; int par[N]; void DSU(){ iota(par+1,par+n+1,1); } int getpar(int u){ return (par[u] == u ? u : par[u] = getpar(par[u])); } void merge(int u,int v){ u=getpar(u),v=getpar(v); if(u==v) return; par[u] = v; } pii E[N]; bool mark[N]; int dis[N]; int pr[N]; vector<int> g[N]; vector<int> sub[N]; void dfs(int u,int p){ mark[u] = 1; pr[u] = p; dis[u] = dis[p] + 1; for(auto h : g[u]){ if(!mark[h]) dfs(h,u); else if(dis[h] < dis[u] and h != p){ int v = u; while(v != h){ merge(v,pr[v]); v = pr[v]; } } } } int dp[N]; int tmp[N]; int ps[N]; int P[N]; int H[N]; void dfs2(int u,int p){ P[u] = p; int head = -1; for(auto h : sub[u]){ for(auto x : g[h]){ if(pr[x] != p and pr[x] != u) dfs2(pr[x],u); if(pr[x] == p ) head = h; } } H[u] = head; if(len(sub[u]) == 1){ dp[u] = 1; for(auto h : g[sub[u][0]]){ if(pr[h] != p) dp[u] = md(dp[u] * md(dp[pr[h]] + 1)); } return; } //cout << u << " -- " << head << endl; //for(auto h : sub[u]) cout << h << sep; //cout << endl; if(head != -1){ for(auto h : sub[u]){ tmp[h] = 1; for(auto x : g[h]){ if(pr[x] != p and pr[x] != u) tmp[h] = md(tmp[h] * md(dp[pr[x]]+1)); } //cout << tmp[h] << sep; } //cout << endl; int tot = 1; for(auto h : sub[u]) tot = md(tot * tmp[h]); int z = 1; ps[sub[u][0]] = 0; for(auto h : sub[u]){ z = md(z * tmp[h]); ps[sub[u][0]] = md(ps[sub[u][0]] + z); } ps[sub[u][0]] = md(ps[sub[u][0]] - tot); for(int i = len(sub[u]) - 1;i > 0;i--){ int nxt = (i+1)%len(sub[u]); ps[sub[u][i]] = md(tmp[sub[u][i]] * md(1 + ps[sub[u][nxt]])); ps[sub[u][i]] = md(ps[sub[u][i]] - tot); } dp[u] = 0; //for(auto h : sub[u]) cout << ps[h] << sep; //cout << endl; for(auto h : sub[u]) dp[u] = md(dp[u] + ps[h]); int ind ; for(int i = 0;i < len(sub[u]);i++){ if(sub[u][i] == head) ind = i; } ind = (ind + 1)%len(sub[u]); vector<int> bad; for(int i = ind;;i = (i+1)%len(sub[u])){ if(sub[u][i] == head) break; bad.pb(sub[u][i]); } int d = 0; //cout << "bad" << endl; //for(auto h : bad) cout << h << sep; //cout << endl; for(auto h : bad){ d = md(tmp[h] * md(d+1)); dp[u] = md(dp[u] - d); } } } int32_t main() { ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0); cin >> n >> m; for(int i =1 ;i<=m;i++){ cin >> E[i].fi >> E[i].sec; if(E[i].sec < E[i].fi) swap(E[i].fi,E[i].sec); g[E[i].fi].pb(E[i].sec); g[E[i].sec].pb(E[i].fi); } DSU(); dfs(1,1); vector<int> st; for(int i = 1;i<=n;i++){ st.pb(getpar(i)); } sort(all(st)); st.resize(unique(all(st)) - st.begin()); for(int i = 1;i<=n;i++){ int v = lower_bound(all(st),getpar(i)) - st.begin() + 1; pr[i] = v; sub[v].pb(i); } for(int i =1 ;i <= len(st);i++){ sort(all(sub[i]),[&](int u,int v){return dis[u] < dis[v];}); } dfs2(pr[1],0); int ans = 0; //for(int i =1 ;i<=len(st);i++) cout << dp[i] << sep; //cout << endl; for(int u = 1;u<=len(st);u++){ if(len(sub[u]) == 1) ans = md(ans + dp[u]); else{ for(auto h : sub[u]){ tmp[h] = 1; for(auto x : g[h]){ if(pr[x] != P[u] and pr[x] != u) tmp[h] = md(tmp[h] * md(dp[pr[x]]+1)); } } //cout << u << " | "; //for(auto h : sub[u]) cout << tmp[h] << sep; //cout << endl; int tot = 1; for(auto h : sub[u]) tot = md(tot * tmp[h]); int z = 1; //cout << tot << endl; ps[sub[u][0]] = 0; for(auto h : sub[u]){ z = md(z * tmp[h]); ps[sub[u][0]] = md(ps[sub[u][0]] + z); } //cout << ps[sub[u][0]] << endl; ps[sub[u][0]] = md(ps[sub[u][0]] - tot); for(int i = len(sub[u]) - 1;i > 0;i--){ int nxt = (i+1)%len(sub[u]); ps[sub[u][i]] = md(tmp[sub[u][i]] * md(1 + ps[sub[u][nxt]])); ps[sub[u][i]] = md(ps[sub[u][i]] - tot); //cout << ps[sub[u][i]] << sep; } //cout << endl; for(auto h : sub[u]) ans = md(ans + ps[h]); } } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...