题面

思路

本蒟蒻第一次学点分治，正遇模板题，留个模板代码
\(Code\)

#include<cstdio>

#include<algorithm>

using namespace std;

const int N = 1e4 + 5;

int len , d[N] , cnt , n , use[N] , h[N] , tot , size , son[N] , siz[N] , rt , ans;

struct edge{

	int to , nxt , w;

}e[2 * N];

inline void add(int x , int y , int z)

{

	e[++tot].to = y;

	e[tot].w = z;

	e[tot].nxt = h[x];

	h[x] = tot;

}

inline void getrt(int x , int fa)

{

	son[x] = 0 , siz[x] = 1;

	for(register int i = h[x]; i; i = e[i].nxt)

	{

		int v = e[i].to;

		if (use[v] || v == fa) continue;

		getrt(v , x);

		siz[x] += siz[v];

		son[x] = max(son[x] , siz[v]);

	}

	son[x] = max(son[x] , size - siz[x]);

	rt = son[x] < son[rt] ? x : rt;

}

inline void getdis(int x , int fa , int dis)

{

	for(register int i = h[x]; i; i = e[i].nxt)

	{

		int v = e[i].to;

		if (use[v] || v == fa) continue;

		d[++cnt] = dis + e[i].w;

		getdis(v , x , d[cnt]);

	}

}

inline int binary(int l , int r , int x)

{

	int mid , res = 0;

	while (l <= r)

	{

		mid = (l + r) >> 1;

		if (d[mid] <= x) res = mid , l = mid + 1;

		else r = mid - 1;

	}

	return res;

}

inline int getans(int x , int dis)

{

	d[cnt = 1] = dis;

	getdis(x , 0 , dis);

	sort(d + 1 , d + cnt + 1);

	int l = 1 , r , res = 0;

	while (len - d[l] >= d[l] && l < cnt)

	{

		r = binary(l + 1 , cnt , len - d[l]);

		if (r > l) res += r - l;

		l++;

	}

	return res;

}

inline void divide(int x)

{

	use[x] = 1 , ans += getans(x , 0);

	for(register int i = h[x]; i; i = e[i].nxt)

	{

		int v = e[i].to;

		if (use[v]) continue;

		ans -= getans(v , e[i].w);

		size = siz[v] , rt = 0;

		getrt(v , x) , divide(rt);

	}

}

int main()

{

	scanf("%d%d" , &n , &len);

	int u , v , w;

	for(register int i = 1; i < n; i++)

	{

		scanf("%d%d%d" , &u , &v , &w);

		add(u , v , w) , add(v , u , w);

	}

	size = n;

	son[0] = 2e9;

	getrt(1 , 0) , divide(rt);

	printf("%d" , ans);

}
巴特西

JZOJ 1166. 树中点对距离

题面

思路

\(Code\)

最新文章

热门文章
