Submission #469872

#	Time	Username	Problem	Language	Result	Execution time	Memory
469872		MohammadParsaElahimanesh	Sumtree (INOI20_sumtree)	C++14	10 / 100	271 ms	45900 KiB

Main

/// 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 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30