自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

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

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

以下是正文

Problem Link

题目大意

给定一棵树，每个点有两个权值 $a_i,b_i$。对于树上的一条简单路径，若这条路径上 $b$ 之和乘上 $a$ 的最小值大于等于一个常数 $V$，那么这条路径被称作一条好的路径，求所有好的路径中，$\sum b$ 的最小值。

数据范围：$n\le 2\times 10^5$。

思路分析

点分治变成 $(B_u+B_v)\min(A_u,A_v)\ge V$，不妨设 $A_u\le A_v$，则只要找到最小的 $B_v\ge \left\lceil \dfrac V{A_u}\right\rceil-B_u$，并且 $u,v$ 来自不同的子树。

那么按 $A$ 降序加入每条路径，按 $B$ 离散化后建树状数组，维护后缀最小值，限制不同的子树就维护不同色的最小值和次小值。

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

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
const ll inf=2e18;
struct info {
	ll v1,v2;
	int c1,c2;
	inline friend info operator +(info u,info v) {
		if(u.v1>v.v1) swap(u,v);
		if(v.c1==u.c1) {
			if(v.v2<u.v2) u.v2=v.v2,u.c2=v.c2;
		} else if(v.v1<u.v2) u.v2=v.v1,u.c2=v.c1;
		return u;
	}
}	tr[MAXN],I={inf,inf,0,0};
int n,tp,siz[MAXN],cur[MAXN];
ll V,a[MAXN],b[MAXN],ans=inf;
vector <int> G[MAXN];
bool vis[MAXN];
ll st[MAXN];
void solve(int u) {
	if(a[u]*b[u]>=V) ans=min(ans,b[u]);
	vector <array<ll,3>> Q;
	for(int v:G[u]) if(!vis[v]) {
		function<void(int,int,ll,ll)> dfs3=[&](int x,int fz,ll mn,ll su) {
			mn=min(mn,a[x]),su+=b[x],Q.push_back({mn,su,v}),siz[x]=1;
			for(int y:G[x]) if(!vis[y]&&y!=fz) dfs3(y,x,mn,su),siz[x]+=siz[y];
		};
		dfs3(v,u,a[u],b[u]);
	}
	tp=0,sort(Q.begin(),Q.end(),greater<>());
	for(auto i:Q) st[++tp]=i[1];
	sort(st+1,st+tp+1),tp=unique(st+1,st+tp+1)-st-1;
	fill(tr,tr+tp+1,I);
	auto add=[&](int x,info v) { for(;x;x&=x-1) tr[x]=tr[x]+v; };
	auto qry=[&](int x) { info s=I; for(;x<=tp;x+=x&-x) s=s+tr[x]; return s; };
	for(auto i:Q) {
		if(i[1]>=(V+i[0]-1)/i[0]) ans=min(ans,i[1]);
		int id=lower_bound(st+1,st+tp+1,(V+i[0]-1)/i[0]-i[1]+b[u])-st;
		info z=qry(id);
		ans=min(ans,i[1]+(z.c1==i[2]?z.v2:z.v1)-b[u]);
		id=lower_bound(st+1,st+tp+1,i[1])-st;
		add(id,{i[1],inf,(int)i[2],0});
	}
}
void dfs1(int u) {
	solve(u),vis[u]=true;
	for(int v:G[u]) if(!vis[v]) {
		int rt=0;
		function<void(int,int)> dfs2=[&](int x,int fz) {
			cur[x]=siz[v]-siz[x];
			for(int y:G[x]) if(y!=fz&&!vis[y]) dfs2(y,x),cur[x]=max(cur[x],siz[y]);
			if(!rt||cur[x]<cur[rt]) rt=x;
		};
		dfs2(v,u),dfs1(rt);
	}
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>V;
	for(int i=1;i<=n;++i) cin>>a[i]>>b[i];
	for(int i=1,u,v;i<n;++i) cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
	dfs1(1),cout<<ans<<"\n";
	return 0;
}