Submission #1266910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266910		mhn_neek	Subtree (INOI20_subtree)	C++20	100 / 100	47 ms	30536 KiB

Main

// 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;
}

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50