自动搬运

查看原文

来自洛谷，原作者为

	Gold14526 nothing

搬运于2025-08-24 23:16:00，当前版本为作者最后更新于2025-03-27 20:57:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

变一下这个式子：

$$\frac{\sum_{x=1}^nf(x,u,v)}{n}\ge \frac{1}{2}\operatorname{dis}(u,v)+k $$$$2\sum_{x=1}^nf(x,u,v)\ge n\times \operatorname{dis}(u,v)+2nk $$$$2\sum_{x=1}^nf(x,u,v)-n\times \operatorname{dis}(u,v)\ge 2nk $$

注意到 $f(x,u,v)+f(x,v,u)=\operatorname{dis}(u,v)$。

所以 $\sum_{x=1}^n(f(x,u,v)+f(x,v,u))=n\times \operatorname{dis}(u,v)$。

于是：

$$2\sum_{x=1}^nf(x,u,v)-\sum_{x=1}^n(f(x,v,u)+f(x,u,v))\ge 2nk $$$$\sum_{x=1}^n(f(x,u,v)-f(x,v,u))\ge 2nk$$

设 $K=2nk$。

注意到 $f(x,u,v)-f(x,v,u)=\operatorname{dis}(x,v)-\operatorname{dis}(x,u)$。

所以：

$$\sum_{x=1}^n(\operatorname{dis}(x,v)-\operatorname{dis}(x,u))\ge K $$

设 $s_u=\sum_{x=1}^n \operatorname{dis}(x,u)$。

则：

$$s_v-s_u\ge K$$

简单换根算出所有点的 $s$ 之后排序，双指针即可。

时间复杂度 $O(n\log n)$，瓶颈在于排序。

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
#define sh short
#define csh const short
#define ush unsigned short
#define cush const unsigned short
using namespace std;
ll read()
{
	ll num=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		num=(num<<1)+(num<<3)+(ch-'0');
		ch=getchar();
	}
	return num;
}
void print(cll x)
{
	if(x<10)
	{
		putchar(x+'0');
		return;
	}
	print(x/10);
	putchar(x%10+'0');
}
void princh(cll x,const char ch)
{
	print(x);
	putchar(ch);
}
int n;
ll k,K;
int head[1000001];
struct edge{
	int to,nxt,val;
}e[2000000];
int tot;
void add_edge(cint u,cint v,cint val)
{
	e[++tot]=edge{u,head[v],val};
	head[v]=tot;
	e[++tot]=edge{v,head[u],val};
	head[u]=tot;
}
int siz[1000001];
ll a[1000001];
void dfs(cint u,cint father,cll dep)
{
	siz[u]=1;
	a[1]+=dep;
	for(int i=head[u];i;i=e[i].nxt)
	{
		if(e[i].to==father)continue;
		dfs(e[i].to,u,dep+e[i].val);
		siz[u]+=siz[e[i].to];
	}
}
void calc(cint u,cint father)
{
	for(int i=head[u];i;i=e[i].nxt)
	{
		if(e[i].to==father)continue;
		a[e[i].to]=a[u]-1ll*siz[e[i].to]*e[i].val+1ll*(n-siz[e[i].to])*e[i].val;
		calc(e[i].to,u);
	}
}
int l;
ll ans;
void solve()
{
	n=read();
	k=read();
	K=n*k<<1;
	tot=ans=0;
	for(int i=1;i<=n;++i)head[i]=0;
	for(int i=1;i<n;++i)
	{
		cint u=read(),v=read(),val=read();
		add_edge(u,v,val);
	}
	dfs(1,0,0);
	calc(1,0);
	sort(a+1,a+n+1);
	l=0;
	for(int i=1;i<=n;++i)
	{
		while(a[l+1]<=a[i]-K)++l;
		ans+=l;
	}
	princh(ans,'\n');
}
int main()
{
	int T=read();
	while(T--)solve();
	return 0;
}