自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:09:52，当前版本为作者最后更新于2019-05-06 15:24:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

点分治+树状数组即可。

树上的路径统计问题，很容易想到点分治。

每次分治的时候，我们对当前连通块，求出所有从根出发的路径的价值。

然后考虑如何合并这些链。

我们把所有的链按照其魔力值排序，然后从小到大枚举。对每条链，设其魔力值为$w$，它与其之前枚举到的链产生的贡献均为$w$。用树状数组来支持单点修改、区间查询，然后对每条链，在树状数组上查询之前有多少满足边数限制的链即可。然后再把这条链放进树状数组里。

注意减去同一棵子树内的贡献。

答案最后乘2即可。

时间复杂度$O(n\log^2 n)$。

Code：

#include<cstdio>
#include<vector>
#include<algorithm>
const int N=1e5+7;
typedef long long LL;
LL ans;
int n,L,R;
struct edge{
	int to,nxt,w;
}e[N<<1];
int head[N],cnt,mx[N],sz[N],all,rt,vis[N];
void getrt(int now,int pre){
	mx[now]=0,sz[now]=1;
	for(int i=head[now];i;i=e[i].nxt)
	if(!vis[e[i].to]&&e[i].to!=pre)getrt(e[i].to,now),sz[now]+=sz[e[i].to],mx[now]=std::max(mx[now],sz[e[i].to]);
	mx[now]=std::max(mx[now],all-sz[now]);
	if(!rt||mx[now]<mx[rt])rt=now;
}
int B[N];
inline void add(int i,int x){for(;i<=R;i+=i&-i)B[i]+=x;}
inline int ask(int i){int x=0;for(;i;i^=i&-i)x+=B[i];return x;}
std::vector<std::pair<int,int>>al,tt;
void dfs(int now,int pre,int len,int val){
	tt.emplace_back(val,len);
	if(len<R)
	for(int i=head[now];i;i=e[i].nxt)
	if(e[i].to!=pre&&!vis[e[i].to])dfs(e[i].to,now,len+1,std::max(val,e[i].w));
}
void doit(int now){
	al.clear();
	for(int i=head[now];i;i=e[i].nxt)if(!vis[e[i].to]){
		tt.clear();
		dfs(e[i].to,now,1,e[i].w);
		std::sort(tt.begin(),tt.end());
		for(int t=0;t<tt.size();++t)
		ans-=(LL)tt[t].first*(ask(R-tt[t].second)-ask(std::max(0,L-tt[t].second-1))),add(tt[t].second,1);
		for(int t=0;t<tt.size();++t)add(tt[t].second,-1);
		for(auto t:tt)al.push_back(t);
	}
	std::sort(al.begin(),al.end());
	for(int t=0;t<al.size();++t)
	ans+=(LL)al[t].first*(ask(R-al[t].second)-ask(std::max(0,L-al[t].second-1))),add(al[t].second,1);
	for(int t=0;t<al.size();++t)add(al[t].second,-1);
	for(auto t:al)
	if(t.second>=L)ans+=t.first;
}
void solve(int now){
	vis[now]=1,doit(now);
	const int sm=all;
	for(int i=head[now];i;i=e[i].nxt)if(!vis[e[i].to]){
		rt=0;
		all=sz[e[i].to]<sz[now]?sz[e[i].to]:sm-sz[now];
		getrt(e[i].to,now),solve(rt);
	}
}
int main(){
	scanf("%d%d%d",&n,&L,&R);
	for(int i=1;i<n;++i){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
		e[++cnt]=(edge){u,head[v],w},head[v]=cnt;
	}
	rt=0,all=n;
	getrt(1,0),solve(rt);
	printf("%lld\n",ans<<1);
	return 0;
}