Submission #587316

#	Time	Username	Problem	Language	Result	Execution time	Memory
587316		lukameladze	Sumtree (INOI20_sumtree)	C++14	0 / 100	110 ms	50924 KiB

Main

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5, mod = 1e9 + 7;
int t,n,a[N],fq[N],inv[N],cnt,r;
vector <int> v[N];
int f_p(int base, int power) {
	int result = 1;
	while (power > 0) {
		if (power % 2) result = (result * base) % mod;
		power /= 2;
		base = (base * base) % mod;
	}
	return result;
}
int C(int n, int k) {
	return (((fq[n] * inv[k])%mod) * inv[n - k]) % mod;
}
/*
*/
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>r;
    fq[0] = 1;
    for (int i = 1; i < N; i++) {
    	fq[i] = (fq[i - 1] * i)%mod;
	}
	inv[N - 1] = f_p(fq[N - 1], mod - 2);
	for (int i = N - 2; i > 1; i--) {
		inv[i] = (inv[i + 1] * (i + 1)) % mod;
	}
	inv[0] = 1;
    for (int i = 1; i <= n - 1; i++) {
    	int a, b;
    	cin>>a>>b;
    	v[a].pb(b);
    	v[b].pb(a);
	}
	cnt = n;
	for (int i = 1; i <= n; i++) {
		if (v[i].size() != 1 || i == 1) {
			// isn't leaf
			cnt++;
			v[i].pb(cnt);
			v[cnt].pb(i);
		}
	}
	n = cnt;
	int lf = 0;
	for (int i = 1; i <= n; i++) {
		if (i != 1 && v[i].size() == 1) lf++;
	}
	int q;
	cin>>q;
	cout<<C(r + lf - 1, lf - 1)<<"\n";
	/*
	
    
    
    
	*/
}

Compilation message (stderr)

Main.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main() {
      | ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30