Submission #634228

#TimeUsernameProblemLanguageResultExecution timeMemory
634228MahdiSubtree (INOI20_subtree)C++17
12 / 100
129 ms23936 KiB
#include<bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() #define F first #define S second typedef long long ll; typedef pair<int, int> pii; const int N=1e5+5, M=1e9+7; int n, m, dis[N], up[N], dn[N], dp[N], pd[N], a[N], b[N], c[N]; vector<int>g[N], kd[N]; bool mk[N]; pii be[N]; inline int tav(int x, int y){ int res=1; while(y){ if(y&1) res=1LL*res*x%M; x=1LL*x*x%M; y>>=1; } return res; } inline int rev(const int &x){ return tav(x, M-2); } void dfs(const int &v, const int &p){ mk[v]=1; be[v]={-1, -1}; for(int u: g[v]){ if(!mk[u]){ dis[u]=dis[v]+1; kd[v].push_back(u); dfs(u, v); if(be[u].S!=-1 && up[be[u].S]!=u) be[v]={u, be[u].S}; } else if(u!=p){ if(dis[u]>dis[v]) dn[v]=u; else up[v]=u; } } if(up[v]!=-1) be[p]={v, v}; } void dfs(const int &v){ for(int u: kd[v]) dfs(u); if(dn[v]==-1){ ll A=0, B=1; for(int u: kd[v]){ A+=dp[u]; B=B*(pd[u]+1)%M; } A+=B; dp[v]=A%M; pd[v]=B; if(be[v].S!=-1){ int u=be[v].F; ll bc=1LL*pd[v]*rev(pd[u]+1)%M; a[v]=bc*(a[u]+1)%M+b[u]; if(a[v]>=M) a[v]-=M; a[v]+=c[u]; if(a[v]>=M) a[v]-=M; b[v]=b[u]*bc%M; c[v]=c[u]+b[v]; if(c[v]>=M) c[v]-=M; } else if(up[v]!=-1){ a[v]=0; c[v]=0; b[v]=pd[v]; } } else{ ll A=0, B=1; for(int u: kd[v]){ A+=dp[u]; if(u!=be[v].F) B=B*(pd[u]+1)%M; else B=B*(a[u]+1)%M; } A+=B; pd[v]=B; dp[v]=A%M; } } int main(){ cin>>n>>m; for(int i=0;i<m;++i){ int u, v; cin>>u>>v; g[--u].push_back(--v); g[v].push_back(u); } memset(up, -1, sizeof(up)); memset(dn, -1, sizeof(dn)); dfs(0, -1); dfs(0); cout<<dp[0]<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...