oj.uz

Submission #469873

# Submission time Handle Problem Language Result Execution time Memory
469873 2021-09-02T08:00:07 Z MohammadParsaElahimanesh Sumtree (INOI20_sumtree) C++14
10 / 100
 287 ms 43500 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 248 ms 43400 KB Output is correct
2 Correct 256 ms 43364 KB Output is correct
3 Correct 258 ms 43304 KB Output is correct
4 Correct 257 ms 43500 KB Output is correct
5 Correct 246 ms 39492 KB Output is correct
6 Correct 91 ms 24132 KB Output is correct
7 Correct 91 ms 23908 KB Output is correct
8 Correct 91 ms 24052 KB Output is correct
9 Correct 250 ms 35772 KB Output is correct
10 Correct 252 ms 35704 KB Output is correct
11 Correct 287 ms 35788 KB Output is correct
12 Correct 235 ms 35140 KB Output is correct
13 Correct 245 ms 42176 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 43400 KB Output is correct
2 Correct 256 ms 43364 KB Output is correct
3 Correct 258 ms 43304 KB Output is correct
4 Correct 257 ms 43500 KB Output is correct
5 Correct 246 ms 39492 KB Output is correct
6 Correct 91 ms 24132 KB Output is correct
7 Correct 91 ms 23908 KB Output is correct
8 Correct 91 ms 24052 KB Output is correct
9 Correct 250 ms 35772 KB Output is correct
10 Correct 252 ms 35704 KB Output is correct
11 Correct 287 ms 35788 KB Output is correct
12 Correct 235 ms 35140 KB Output is correct
13 Correct 245 ms 42176 KB Output is correct
14 Incorrect 89 ms 23748 KB Output isn't correct
15 Halted 0 ms 0 KB -