Submission #633523

#	Time	Username	Problem	Language	Result	Execution time	Memory
633523		MatBad	Subtree (INOI20_subtree)	C++14	100 / 100	103 ms	21504 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=a; i<=b; i++)
#define FORR(i, a, b) for(int i=a; i>=b; i--)
#define pb push_back
#define ppb pop_back
#define lc 2*u
#define rc 2*u+1
#define mid ((l+r)/2)
#define F first
#define S second
#define debug(x) cerr<<"$ "<<#x<<" : "<<x<<" $\n"
#define wall() cerr<<"\n----------------------\n"

typedef long long ll;
typedef pair<ll, int> pii;

const ll MX=1e5+5, M=1e9+5, LG=19, inf=1e9+5, MOD=1e9+7;

ll n, m, dp[2][MX], N, beg[MX], p[MX];
vector<int> adj[MX], adjt[MX];
pii e[MX];
bool mark[MX], m1[MX];

void dd(int u, int par=0){
	m1[u]=mark[u]=true;
	adj[par].pb(u), p[u]=par;
	for(int v:adjt[u]) if(v!=par){
		if(!m1[v]) dd(v, u);
		else if(mark[v]){
			N++;
			beg[v]=N;
			e[N] = pii(v, u);
		}
	}
	mark[u]=false;
}

pii solve(int k){
	pii res;
	vector<int> vec;
	for(int v=e[k].S; v!=e[k].F; v=p[v]){
		vec.pb(v);
	}
	int t=(int)vec.size();
	//FOR(i, 0, t-1) debug(vec[i]);
	res.S = vec[t-1];
	ll f[3][t+5];
	f[0][0]=0;
	f[1][0]=1;
	f[2][0]=dp[1][vec[0]];
	FOR(i, 1, t-1){
		f[1][i] = (f[1][i-1]+f[2][i-1])%MOD;
		ll d=1;
		for(int v:adj[vec[i]]) if(v!=vec[i-1]) d=d*(dp[1][v]+1)%MOD;
		f[0][i] = d*(f[0][i-1]+f[1][i-1])%MOD;
		f[2][i] = d*f[2][i-1]%MOD;
		//debug(vec[i]);
		//FOR(j, 0, 2) debug(f[j][i]);
	}
	FOR(i, 0, 1) res.F = (res.F+f[i][t-1]);
	return res;
}

void dfs(int u){
	for(int v:adj[u]){
		dfs(v);
		dp[0][u] = (dp[0][u]+dp[0][v]+dp[1][v])%MOD;
		
	}
	
	dp[1][u] = 1;
	pii g = pii(0, 0);
	if(beg[u]){
		g = solve(beg[u]);
		dp[1][u] = g.F;
	}
	for(int v:adj[u]) if(v!=g.S){
		dp[1][u] = dp[1][u]*(dp[1][v]+1)%MOD;
	}
	//debug(u<<' '<<dp[0][u]<<' '<<dp[1][u]);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	FOR(i, 1, m) {
		int u, v;
		cin>>u>>v;
		adjt[u].pb(v);
		adjt[v].pb(u);
	}
	dd(1);
	dfs(1);
	cout<<(dp[0][1]+dp[1][1])%MOD<<'\n';
}

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