제출 #634289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
634289		S2speed	Subtree (INOI20_subtree)	C++17	12 / 100	59 ms	9932 KiB

Main

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

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