Submission #1265792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265792		mhn_neek	Subtree (INOI20_subtree)	C++20	12 / 100	37 ms	21808 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 = 5e5 + 100;
const lli mod = 1e9+7;
const lli INF = 1e18;
#define PB push_back
#define MP make_pair
#define fi first
#define se second
#define debug(x) cerr<<(#x)<<" "<<x<<endl
#define FOR(x,y) for(lli x = 0; x < y ;x++)
#define FORS(x,y) for(lli x = 1; x <= y ;x++)
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(),x.end()
lli n,m;
ve adj[N];
lli dp[N];

void dfs(lli u,lli par = 0){
	dp[u] = 1;
	for(lli v : adj[u]){
		if(v != par){
			dfs(v,u);
			dp[u] = dp[u]*(dp[v]+1)%mod;
		}
	}
}

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);
	}
	if(m > n-1)exit(0);
	dfs(1);
	lli ans = 0;
	FORS(i,n)
		ans = (ans + dp[i])%mod;
	cout<<ans<<endl;

}

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