C++(clang++11) 解法, 执行用时: 1224ms, 内存消耗: 22684K, 提交时间: 2020-10-28 23:57:34

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 100050;
template<typename T>inline void read(T&x)
{
	T f = 1,c = 0;char ch = getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
	x = f*c;
}
struct Pair
{
	int x,y;
	Pair(){}
	Pair(int x,int y):x(x),y(y){}
	bool operator < (const Pair&p)const{return x<p.x;}
};
vector<Pair>ve[N];
int T,n,m;
int siz[N],fa[N],mx_siz[N],rt,sum;
bool use[N];
void get_rt(int u,int ff=0)
{
	fa[u] = ff,siz[u] = 1,mx_siz[u] = 0;
	for(int i=0;i<ve[u].size();i++)
	{
		int to = ve[u][i].y;
		if(to==ff||use[to])continue;
		get_rt(to,u);
		siz[u] += siz[to];
		if(siz[to]>mx_siz[u])
			mx_siz[u] = siz[to];
	}
	mx_siz[u] = max(mx_siz[u],sum-siz[u]);
	if(mx_siz[u]<mx_siz[rt])rt=u;
}
int tin[N],tout[N],pla[N],tim,dep[N],col[N],tl;
ll w[N],w1[N],w2[N],ans,tmp[N];
ll sta[N],sta2[N];
ll calc(int d,int l){return l>2?0:1ll*d*l;}
void dfs(int u,int ff,ll s,int d,int l)
{
	tin[u] = ++tim,pla[tim] = u,w[tim] = s+calc(d,l);
	dep[u] = dep[ff]+1;
	if(dep[u]!=l+1)w1[u]=w1[ff];
	else w1[u] = calc(d,l);
	for(int i=0;i<ve[u].size();i++)
	{
		int to = ve[u][i].y;
		if(to==ff||use[to])continue;
		if(!ff)col[to]=ve[u][i].x;
		else col[to]=col[u];
		if(ve[u][i].x!=d)dfs(to,u,s+calc(d,l)-m,ve[u][i].x,1);
		else dfs(to,u,s-m,d,l+1);
	}
	tout[u] = tim;
}
ll calc(int u,int ff,ll s,int d,int l)
{
	dep[u] = (ff!=0);tim = 0;
	dfs(u,ff,s,d,l);
	ll ret = 0;int lw;
	for(int i=1;i<=tim;i++)
		w2[i] = w[i] - w1[pla[i]];
	for(int i=1;i<=tim;i++)
	{
		if(col[pla[i]]==w1[pla[i]])sta[++tl] = w[i],sta2[tl] = w2[i];
		if(i==tim||col[pla[i]]!=col[pla[i+1]])
		{
			sort(sta+1,sta+tl+1);
			int lk = 1,rk = tl+1;//w(1,1)
			for(;lk<=tl;lk++)
			{
				while(rk-1>=1&&sta[lk]+sta[rk-1]>=0)rk--;
				ret += tl+1-max(rk,lk+1);
			}
			sort(sta2+1,sta2+tl+1);
			lk = 1,rk = tl+1;//w2(1,1)
			for(;lk<=tl;lk++)
			{
				while(rk-1>=1&&sta2[lk]+sta2[rk-1]>=0)rk--;
				ret -= tl+1-max(rk,lk+1);
			}
			tl = 0;
		}
	}
	lw = (ff==0);//w(a,b)
	for(int i=lw+1;i<=tim;i++)if(i==tim||col[pla[i]]!=col[pla[i+1]])
	{
		sort(w+lw+1,w+i+1);
		int lk = lw+1,rk = i+1;
		for(;lk<=i;lk++)
		{
			while(rk-1>=lw+1&&w[lk]+w[rk-1]>=0)rk--;
			ret -= i+1-max(rk,lk+1);
		}
		lw = i;
	}
	lw = (ff==0);//w2
	for(int i=lw+1;i<=tim;i++)if(i==tim||col[pla[i]]!=col[pla[i+1]])
	{
		sort(w2+lw+1,w2+i+1);
		int lk = lw+1,rk = i+1;
		for(;lk<=i;lk++)
		{
			while(rk-1>=lw+1&&w2[lk]+w2[rk-1]>=0)rk--;
			ret += i+1-max(rk,lk+1);
		}
		lw = i;
	}
	sort(w+1,w+1+tim);//w
	int lk = 1,rk = tim+1;
	for(;lk<=tim;lk++)
	{
		while(rk-1>=1&&w[lk]+w[rk-1]>=0)rk--;
		ret += tim+1-max(rk,lk+1);
	}
	return ret;
}
void clear()
{
	ans = 0;
	for(int i=1;i<=n;i++)
	{
		use[i] = col[i] = 0;
		ve[i].clear();
	}
}
void work()
{
	ans+=calc(rt,0,0,0,0);
	use[rt] = 1;int u = rt;
	for(int i=0;i<ve[u].size();i++)
	{
		int to = ve[u][i].y;
		if(use[to])continue;
		ans -= calc(to,u,-m,ve[u][i].x,1);
	}
	for(int i=0;i<ve[u].size();i++)
	{
		int to = ve[u][i].y;
		if(use[to])continue;
		sum = siz[to];rt = 0;
		get_rt(to);work();
	}
}
void sol()
{
	clear();
	read(n),read(m);
	for(int u,v,w,i=1;i<n;i++)
		read(u),read(v),read(w),ve[u].push_back(Pair(w,v)),ve[v].push_back(Pair(w,u));
	for(int i=1;i<=n;i++)
		sort(ve[i].begin(),ve[i].end());
	rt=0,sum=n;
	get_rt(1);work();
	printf("%lld\n",ans);
}
int main()
{
	read(T);mx_siz[0] = 0x3f3f3f3f;
	while(T--)sol();
	return 0;
}