CF293E Close Vertices

对于这种树上路径统计问题，一个经典解法就是点分治。

如果没有两个限制，还是很简单的，对于单个限制，使用树状数组来解决就行了。

但是这道题目要求两个限制，有点像二维偏序，但不完全是。可以说是分成了几个段，每个段之间求二维偏序，而要求段内不能产生贡献。如果这么表述这个问题的话，那就很好解决了：把段内的贡献先求出来，再求出总的贡献，减去即可。

但是如果在表述问题时用：子树内与已经记录的桶内的贡献，那么就死路一条了。

这给了两个启示：1.点分治不要拘泥于每个子树与已经记录的桶之间的关系。2.尝试转化问题，把问题用比较形式化的语言表述出来（比如“子树”这个说法，其实它是不是个树无所谓）。

注意有个易错点：不要搞混了限制中的 \(l,w\) 与双指针中的 \(l\)，边权的 \(w\)。

#include <bits/stdc++.h>

using namespace std;

#define typ int
inline char gc(){static char buf[100000] , *p1 = buf , *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 100000 , stdin) , p1 == p2) ? EOF : *p1 ++ ;}inline typ read(){typ x = 0; bool f = 0;char ch = gc();while(!isdigit(ch)){f |= (ch == '-');ch = gc();}while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = gc();}return (f ? -x : x);}

typedef long long ll;

const int N = 1e5 + 5;

int n , L , W;
vector<pair<int,int> > E[N];

int siz[N] , dis[N] , wsum[N] , mk[N];
pair<int,int> buc[N] , Buc[N]; int o , O;

namespace BIT {
#define lowbit(x) (x & (-x))
	int t[N];
	void add(int x , int v){
		while(x <= n){
			t[x] += v;
			x += lowbit(x);
		}
	}
	ll qwq(int x){
		if(x < 0) return 0;
		ll res = 0;
		while(x){
			res += t[x];
			x -= lowbit(x);
		}
		return res;
	}
}

signed main(){
	n = read() , L = read() , W = read();
	
	for(int i = 2; i <= n; ++ i){
		int v = read() , w = read();
		E[i].push_back({v , w});
		E[v].push_back({i , w});
	}
	
	int rt , sum;
	function<void(int,int)> getrt = [&] (int u , int fa){
		siz[u] = 1;
		int maxs = 0;
		for(auto e : E[u]){
			int v = e.first;
			if(v == fa || mk[v]) continue;
			
			getrt(v , u);
			
			siz[u] += siz[v];
			maxs = max(maxs , siz[v]);
		}
		maxs = max(maxs , sum - siz[u]);
		if(maxs <= sum / 2) rt = u;
	};
	
	function<void(int,int)> getdis = [&] (int u , int fa){
		buc[ ++ o] = {wsum[u] , dis[u]};
		for(auto e : E[u]){
			int v = e.first , w = e.second;
			if(v == fa || mk[v]) continue;
			
			dis[v] = dis[u] + 1;
			wsum[v] = wsum[u] + w;
			
			getdis(v , u);
		}
	};
	
	ll ans = 0;
	function<void(int)> calc = [&] (int u){
		O = 0;
		for(auto e : E[u]){
			int v = e.first , w = e.second;
			if(mk[v]) continue;
			
			wsum[v] = w , dis[v] = 1;
			o = 0;
			getdis(v , u);
			
			sort(buc + 1 , buc + o + 1);
			for(int i = 2; i <= o; ++ i) BIT::add(buc[i].second , 1);
			for(int i = 1; i <= o; ++ i) Buc[ ++ O] = buc[i];
			for(int l = 1 , r = o; l < r; ){// calculating l , r is border
				while(l < r && buc[r].first + buc[l].first > W) BIT::add(buc[r -- ].second , -1);
				ans -= BIT::qwq(L - buc[l].second);
				if( ++ l <= r) BIT::add(buc[l].second , -1);
			}
		}
		Buc[ ++ O] = {0 , 0};
		sort(Buc + 1 , Buc + O + 1);
		for(int i = 2; i <= O; ++ i) BIT::add(Buc[i].second , 1);
		for(int l = 1 , r = O; l < r;){// calculating l , r is border
			while(l < r && Buc[r].first + Buc[l].first > W) BIT::add(Buc[r -- ].second , -1);
			ans += BIT::qwq(L - Buc[l].second);
			if( ++ l <= r) BIT::add(Buc[l].second , -1);
		}
	};
	
	function<void(int)> work = [&] (int u) {
		mk[u] = 1;
		calc(u);
		for(auto e : E[u]){
			int v = e.first;
			if(mk[v]) continue;
			
			getrt(v , u);
			sum = siz[v];
			getrt(v , u);
			
			work(rt);
		}
	};
	
	sum = n;
	getrt(1 , 0);
	
	work(rt);
	
	printf("%lld" , ans);
	
	return 0;
}