oj.uz

Submission #469872

# Submission time Handle Problem Language Result Execution time Memory
469872 2021-09-02T07:59:46 Z MohammadParsaElahimanesh Sumtree (INOI20_sumtree) C++14
10 / 100
 271 ms 45900 KB 
/// In the name of Allah

#include <bits/stdc++.h>

using namespace std;

#define Fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define RFOR(i,a) for(int i = a-1; i >= 0; i--)
#define FOR(i,a) for(int i = 0; i < a; i++)
#define se second
#define fi first
#define sz(x) (int)x.size()
#define upp upper_bound
#define low lower_bound
#define pub push_back
#define all(x) x.begin(),x.end()
#define mp make_pair

typedef double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

const ll mod = 1'000'000'007;
const int N = 200'000 + 5;
const int Z = 500'000 + 5;
ll F[Z], _F[Z], ans;
int n, r, q, H[N], S[N], dad[N], st[N], en[N], R[N], B[N], timer = 1, p = 0;
set<int> X[N];
vector<int> G[N];

inline ll Pow(ll a, int b)
{
	ll res = 1LL;
	while(b)
	{
		if(b&1)res = res*a%mod;
		b >>= 1;
		a = a*a%mod;
	}
	return res;
}

inline ll inv(int x){return Pow(x,mod-2);}

inline ll C(int x, int y)
{
	if(x > y || x < 0)return 0;
	return F[y]*_F[x]%mod*_F[y-x]%mod;
}

struct fen
{
	int G[N];
	fen(){memset(G,0,sizeof(G));}
	inline void inc(int p, int x)
	{
		while(p < N)
		{
			G[p] += x;
			p += p&-p;
		}
	}
	inline int get(int p)
	{
		int s = 0;
		while(p)
		{
			s += G[p];
			p -= p&-p;
		}
		return s;
	}
}tags, Free;


int dfs_s(int v, int d, int h)
{
	st[v] = timer++;
	H[v] = h;
	dad[v] = d;
	S[v] = 1;
	for(auto u: G[v])if(u != d)S[v] += dfs_s(u,v,h+1);
	en[v] = timer;
	return S[v];
}

void dfs_hld(int v, int top, int nam)
{
	R[v] = nam;
	B[v] = top;
	pii MAX = mp(-1,-2);
	for(auto u: G[v])if(u != dad[v])MAX = max(MAX,mp(S[u],u));
	for(auto u: G[v])if(u != dad[v])
	{
		if(MAX.se == u)dfs_hld(u,top,nam);
		else dfs_hld(u,u,p++);
	}
}

int main()
{
	Fast
	
	F[0] = 1;
	for(ll i = 1; i < Z; i++)F[i] = i*F[i-1]%mod;
	FOR(i,Z)_F[i] = inv(F[i]);
	
	cin >> n >> r;
	
	int u, v;
	FOR(i,n-1)
	{
		cin >> u >> v;
		u--; v--;
		G[u].pub(v); G[v].pub(u);
	}
	dfs_s(0,0,0);
	dfs_hld(0,0,p++);
	
	tags.inc(st[0],r);
	Free.inc(st[0],n);
	ans = C(r,n+r-1);
	cout << ans;
	
	return 0;
}

// thank god

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 45764 KB Output is correct
2 Correct 270 ms 45900 KB Output is correct
3 Correct 253 ms 45764 KB Output is correct
4 Correct 271 ms 45828 KB Output is correct
5 Correct 229 ms 41924 KB Output is correct
6 Correct 90 ms 24196 KB Output is correct
7 Correct 91 ms 23944 KB Output is correct
8 Correct 90 ms 24056 KB Output is correct
9 Correct 250 ms 38224 KB Output is correct
10 Correct 252 ms 38084 KB Output is correct
11 Correct 252 ms 38244 KB Output is correct
12 Correct 235 ms 37444 KB Output is correct
13 Correct 239 ms 44332 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 45764 KB Output is correct
2 Correct 270 ms 45900 KB Output is correct
3 Correct 253 ms 45764 KB Output is correct
4 Correct 271 ms 45828 KB Output is correct
5 Correct 229 ms 41924 KB Output is correct
6 Correct 90 ms 24196 KB Output is correct
7 Correct 91 ms 23944 KB Output is correct
8 Correct 90 ms 24056 KB Output is correct
9 Correct 250 ms 38224 KB Output is correct
10 Correct 252 ms 38084 KB Output is correct
11 Correct 252 ms 38244 KB Output is correct
12 Correct 235 ms 37444 KB Output is correct
13 Correct 239 ms 44332 KB Output is correct
14 Incorrect 89 ms 23752 KB Output isn't correct
15 Halted 0 ms 0 KB -