Submission #634289

#TimeUsernameProblemLanguageResultExecution timeMemory
634289S2speedSubtree (INOI20_subtree)C++17
12 / 100
59 ms9932 KiB
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")

#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;

const ll maxn = 1e5 + 17 , md = 1e9 + 7 , inf = 2e16;

ll n , m;
ll dp[maxn];
vector<ll> adj[maxn];

void dDFS(ll r , ll par){
	ll h = 1;
	for(auto i : adj[r]){
		if(i == par) continue;
		dDFS(i , r);
		h *= dp[i] + 1; h %= md;
	}
	dp[r] = h;
	return;
}

void sub2(){
	for(ll i = 1 ; i < n ; i++){
		ll v , u;
		cin>>v>>u; v--; u--;
		adj[v].push_back(u); adj[u].push_back(v);
	}
	dDFS(0 , -1);
	ll ans = 0;
	for(ll i = 0 ; i < n ; i++) ans += dp[i];
	ans %= md;
	cout<<ans<<'\n';
	return;
}

void sub1(){
	return;
}

int main(){
	ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);

	cin>>n>>m;
	if(m == n - 1) sub2();
	sub1();
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...