Submission #1266910

#TimeUsernameProblemLanguageResultExecution timeMemory
1266910mhn_neekSubtree (INOI20_subtree)C++20
100 / 100
47 ms30536 KiB
// IN THE NAME OF GOD
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N = 3e5 + 10;
const lli mod = 1e9 + 7;
const lli INF = 1e18;
#define PB push_back
#define MP make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define FOR(x,y) for(lli x = 0; x  < y;  x++)
#define FORS(x,y) for(lli x = 1; x  <= y;  x++)
#define debug(x) cerr<<(#x)<<" "<<x<<endl
lli n,m;
ve adj[N];
lli dp[N],par[N],h[N];
bool vis[N];

void dfs(lli v){
	vis[v] = 1;
	dp[v] = 1;
	lli back_edge = -1;
	for(lli u : adj[v]){
		if(u == par[v])continue;
		if(vis[u] == 0){
			par[u] = v;
			h[u] = h[v] + 1;
			dfs(u);
			dp[v] = (dp[v]* (dp[u] + 1))%mod;
		}
		else if(h[u] > h[v]){
			back_edge = u;
		}
	}
	
	if(back_edge == -1)return;

	//--------------------
	dp[v] = 0;
	ve path;
	lli ver = back_edge;
	path.PB(back_edge);
	while(ver != v){
		ver = par[ver];
		path.PB(ver);
	}
	reverse(all(path));
	lli exc  = 1;
	for(lli u : adj[v])if(u != par[v] && u != back_edge && u != path[1])exc = (exc*(dp[u]+1))%mod;

	lli m = path.size();
	ve f(m),g(m);
	f[0] = exc;
	g[0] = f[0];
	FORS(i,m-2){
		f[i] = f[i-1];
		for(auto u : adj[path[i]])if(u != path[i+1] && u != par[path[i]])f[i] = (f[i]*(dp[u]+1))%mod;
		g[i] = (g[i-1] + f[i])%mod;
	}
	dp[v] = (dp[v] + g[m-2])%mod;
	exc = dp[back_edge];//*g[m-3];
	dp[v] = (dp[v] + exc * g[m-3]%mod)%mod;
	for(lli i=m-2; i > 1; i --){
		for(auto u : adj[path[i]])if(u != path[i+1] && u != par[path[i]])exc = (exc * (dp[u]+1))%mod;
		dp[v] = (dp[v] + exc*g[i-2]%mod)%mod;
	}

	/*debug(v);
	debug(back_edge);
	debug(dp[v]);*/
}



int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	FOR(i,m){
		lli a,b;
		cin>>a>>b;
		adj[a].PB(b);
		adj[b].PB(a);
	}
	dfs(1);
	lli ans = 0;
	FORS(i,n)
		ans = (ans + dp[i])%mod;

	cout<<ans<<endl;
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...