oj.uz

Submission #789152

# Submission time Handle Problem Language Result Execution time Memory
789152 2023-07-21T06:42:41 Z MISM06 Sumtree (INOI20_sumtree) C++14
10 / 100
 148 ms 56040 KB 
//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2")

using namespace std;

#define F 			first
#define S 			second
#define pb 			push_back
#define sze			size()
#define	all(x)		x.begin() , x.end()
#define wall__		cout << "--------------------------------------\n";
#define kids		int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io		freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);

typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;


const ll N = 2e5 + 10, M = 5e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 2e16;
const ll INF = 1e9 + 10;
const ll lg = 32;

ll fac[M], inv[M];
inline void add (ll &x, ll y) {
	x += y; if (x >= mod) x -= mod;
	if (x < 0) x += mod;
}
inline ll Sum (ll x, ll y) {
	x += y; if (x >= mod) x -= mod;
	if (x < 0) x += mod;
	return x;
}
inline ll mul (ll x, ll y) {
	x *= y; x %= mod; if (x < 0) x+= mod;
	return x;
}
inline ll pw (ll x, ll y) {
	ll res = 1;
	while(y) {
		if (y & 1) res = mul(res, x);
		x = mul(x, x);
		y >>= 1;
	}
	return res;
}
inline ll choose (ll x, ll y) {
	if (x < y || y < 0) return 0;
	return mul(fac[x], mul(inv[y], inv[x - y]));
}

ll n,  chp[N], par[N], hv[N], h[N], sub[N], chs[N], ANS;
ll a[N], st[N], en[N], timer = 0, ct[N], bit[N], rs[N], c0;
set < pii > s[N];
vector < int > g[N];
bool is[N];

inline ll read (int idx) {
	ll res = 0;
	for (; idx > 0; idx -= (idx & -idx)) res += bit[idx];
	return res;
}
inline void upd (int idx, ll val) {
	for (; idx <= n; idx += (idx & -idx)) 
		bit[idx] += val;
}
inline ll range (int l, int r) {
	return read(r) - read(l - 1);
}
void dfs0 (int v, int p) {
	par[v] = p;
	h[v] = h[p] + 1;
	st[v] = ++timer;
	sub[v] = 1;
	for (auto u : g[v]) {
		if (u == p) continue;
		dfs0(u, v);
		sub[v] += sub[u];
		if (sub[u] > sub[hv[v]]) hv[v] = u;
	}
	en[v] = timer;
}
void dfs (int v, int p) {
	chs[v] = v;
	for (auto u : g[v]) {
		if (u == p) continue;
		if (hv[v] == u) chp[u] = chp[v];
		else chp[u] = u;
		dfs(u, v);
		if (hv[v] == u) chs[v] = chs[u];
	}
}

void solve () {

	cin >> n >> a[1];
	for (int i = 1; i < n; i++) {
		int v, u; cin >> v >> u;
		g[v].pb(u); g[u].pb(v);
	}
	chp[1] = 1;
	dfs0(1, 0);
	dfs(1, 0);
	for (int i = 2; i <= n; i++) {
		ct[i] = 1;
		upd(st[i], 1);
	}
	ct[1] = n; upd(st[1], n);
	fill(rs, rs + N, -1);
	rs[1] = choose(a[1] + ct[1] - 1, ct[1] - 1);
	cout << rs[1] << '\n';
	int q; cin >> q;
	while(q--) {
		cout << 0 << '\n';
	}


}


int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	fac[0] = 1;
	for (int i = 1; i < M; i++) fac[i] = mul(fac[i - 1], i);
	inv[M - 1] = pw(fac[M - 1], mod - 2);
	for (int i = M - 2; i >= 0; --i) inv[i] = mul(inv[i + 1], i + 1);
	int t = 1;
	// cin >> t;
	while (t--) {solve();}
    return 0;
}
/*
*/
//shrek is love;

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 55940 KB Output is correct
2 Correct 122 ms 55992 KB Output is correct
3 Correct 111 ms 56040 KB Output is correct
4 Correct 132 ms 55948 KB Output is correct
5 Correct 98 ms 52032 KB Output is correct
6 Correct 15 ms 24424 KB Output is correct
7 Correct 18 ms 24140 KB Output is correct
8 Correct 15 ms 24276 KB Output is correct
9 Correct 148 ms 48384 KB Output is correct
10 Correct 119 ms 48216 KB Output is correct
11 Correct 130 ms 48360 KB Output is correct
12 Correct 121 ms 47068 KB Output is correct
13 Correct 126 ms 53528 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 23780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 55268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 48932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 55940 KB Output is correct
2 Correct 122 ms 55992 KB Output is correct
3 Correct 111 ms 56040 KB Output is correct
4 Correct 132 ms 55948 KB Output is correct
5 Correct 98 ms 52032 KB Output is correct
6 Correct 15 ms 24424 KB Output is correct
7 Correct 18 ms 24140 KB Output is correct
8 Correct 15 ms 24276 KB Output is correct
9 Correct 148 ms 48384 KB Output is correct
10 Correct 119 ms 48216 KB Output is correct
11 Correct 130 ms 48360 KB Output is correct
12 Correct 121 ms 47068 KB Output is correct
13 Correct 126 ms 53528 KB Output is correct
14 Incorrect 16 ms 23780 KB Output isn't correct
15 Halted 0 ms 0 KB -