传送门

先点分值,求重心分治下去

然后考虑如何计算点 u u u的贡献

首先我们暴力计算出 u u u子树中到 u u u的所有距离放在数组里

排序后,双指针可以快速计算多少条路径的拼接小于等于 k k k

但是会有重复,存在两条路径都在一颗子树内部

那就容斥,对子树也计算一遍,减去子树的答案即可,减去的都是多加的

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
struct edge
{
	int to,nxt,w;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v,int w){ d[++cnt] = (edge){v,head[u],w},head[u] = cnt; }
int n,k,sumn,root,rem[maxn],ans,siz[maxn],mx[maxn],vis[maxn];
void getroot(int u,int fa)
{
	siz[u] = 1; mx[u] = 0;
	for(int i=head[u];i;i=d[i].nxt )
	{
		int v = d[i].to;
		if( vis[v] || v==fa )	continue;
		getroot(v,u);
		siz[u] += siz[v];
		mx[u] = max( mx[u],siz[v] );
	}
	mx[u] = max( mx[u],sumn-siz[u] );
	if( mx[u]<mx[root] )	root = u;
}
void get_dis(int u,int fa,int zhi)
{
	rem[++rem[0]] = zhi;
	for(int i=head[u];i;i=d[i].nxt )
	{
		int v = d[i].to;
		if( v==fa||vis[v] )	continue;
		get_dis(v,u,zhi+d[i].w);
	}
} 
int calc(int u,int w)//计算经过点u为根的全部答案 
{
	rem[0] = 0; get_dis(u,0,w);
	sort( rem+1,rem+1+rem[0] );
	int l = 1,r = rem[0],ans = 0;
	while( r>=l )
	{
		if( rem[l]+rem[r]<=k )	ans += r-l,l++;
		else	r--;
	}
	return ans;
}
void solve(int u)
{
	vis[u] = 1; ans += calc(u,0);
	for(int i=head[u];i;i=d[i].nxt )
	{
		int v = d[i].to;
		if( vis[v] )	continue;
		ans -= calc(v,d[i].w);
		sumn = siz[v], mx[root=0] = n;
		getroot(v,u); solve(root);
	}
}
int main()
{
	cin >> n;
	for(int i=1;i<n;i++)
	{
		int l,r,w; scanf("%d%d%d",&l,&r,&w);
		add(l,r,w); add(r,l,w);
	}
	cin >> k;
	sumn = mx[root=0] = n;
	getroot(1,0); solve(root);
	cout << ans;
}