Seletiva IOI 2013

passeio.cpp

// Ivan Carvalho
// Passeio - Seletiva IOI - OBI 2013
#include <bits/stdc++.h>
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef struct node* pnode;
typedef vector<ll>::iterator ite;
const ll MAXN = 1e5 + 10;
struct node{
	pnode l,r;
	ii key;
	ll prior,size;
	node(ii key) : key(key),size(1),prior(rand()),l(NULL),r(NULL){}
};
inline ll sz(pnode t){
	if(t == NULL) return 0;
	return t->size;
}
inline void upd_sz(pnode t){
	if(t) t->size = sz(t->l) + 1 + sz(t->r);
}
void split(pnode t,ii key,pnode &l,pnode &r){
	if(t == NULL){
		l = r = NULL;
	}
	else if(key < t->key){
		split(t->l,key,l,t->l);
		r = t;
	}
	else{
		split(t->r,key,t->r,r);
		l = t;
	}
	upd_sz(t);
}
void merge(pnode &t,pnode l,pnode r){
	if(l == NULL){
		t =r;
	}
	else if(r == NULL){
		t = l;
	}
	else if(l->prior > r->prior){
		merge(l->r,l->r,r);
		t = l;
	}
	else{
		merge(r->l,l,r->l);
		t = r;
	}
	upd_sz(t);
}
void insert(pnode &t,ii key){
	pnode L,R;
	pnode aux = new node(key);
	split(t,MP(key.first-1,MAXN),L,R);
	merge(t,L,aux);
	merge(t,t,R);
}
ll query(pnode t,ii key){
	if(t == NULL) return 0;
	if(key < t->key){
		return query(t->l,key);
	}
	if(key == t->key){
		return sz(t->l) + 1;
	}
	return sz(t->l) + 1 + query(t->r,key);
}
vector<ll> grafo[MAXN];
vector<ll> *conjunto[MAXN];
pnode raiz[MAXN];
ll tam[MAXN],nivel[MAXN],resp[MAXN],ac[MAXN],N,A,B;
void dfs_sack(ll v,ll p){
	tam[v] = 1;
	ll big = -1,mx = -1;
	for(ll i=0;i<grafo[v].size();i++){
		ll u = grafo[v][i];
		if(u != p){
			nivel[u] = nivel[v] + 1;
			dfs_sack(u,v);
			tam[v] += tam[u];
			if(tam[u] > mx){
				mx = tam[u];
				big = u;
			}
		}
	}
	if(big == -1){
		raiz[v] = new node(MP(0,v));
		conjunto[v] = new vector<ll> ();
		(*conjunto[v]).push_back(v);
	}
	else{
		raiz[v] = raiz[big];
		ac[v] = ac[big] + 1;
		resp[v] += query(raiz[v],MP(B - ac[v],MAXN)) - query(raiz[v],MP(A - ac[v] - 1,MAXN));
		insert(raiz[v],MP(-ac[v],v));
		conjunto[v] = conjunto[big];
		(*conjunto[v]).push_back(v);
	}
	for(ll i=0;i<grafo[v].size();i++){
		ll u = grafo[v][i];
		if(u != p && u != big){
			for(ite it = (*conjunto[u]).begin();it != (*conjunto[u]).end();it++){
				ll x = *it;
				ll dist = nivel[x] - nivel[v];
				resp[v] += query(raiz[v],MP(B - ac[v] - dist,MAXN)) - query(raiz[v],MP(A - ac[v] - 1 - dist,MAXN));
			}
			for(ite it = (*conjunto[u]).begin();it != (*conjunto[u]).end();it++){
				ll x = *it;
				ll dist = nivel[x] - nivel[v];
				insert(raiz[v],MP(dist - ac[v],x));
				(*conjunto[v]).push_back(x);
			}
		}
	}
}
int main(){
	scanf("%lld",&N);
	for(ll i=1;i<N;i++){
		ll u,v;
		scanf("%lld %lld",&u,&v);
		u++;
		v++;
		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}
	scanf("%lld %lld",&A,&B);
	long long exibir = 0;
	dfs_sack(1,-1);
	for(ll i=1;i<=N;i++) exibir += resp[i];
	printf("%lld\n",exibir); 
	return 0;
}