树上主席树练手题。

对于单次询问，可以取出路径上所有的检查点，贪心地选取 $c_j$ 更小的点付银币，剩下的检查点付金币。

拓展到多次询问，我们想要快速地获得一条路径上检查站形成的桶。

仿照序列上获得区间桶信息的方法，我们建出主席树，每个节点上的版本维护其到根的链上的信息。这样，我们只需使用树上差分，用 $u,v,\operatorname{LCA}(u,v)$ 版本的树相加减即可得到路径信息。

$n,m,q$ 同阶，时空复杂度均为 $O(n \log n)$。

如果想要再做一道练手，可以尝试 P2633 Count on a tree。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+6;
typedef long long i64;
int n,m,q;
vector<pair<int,int> > f[N];
vector<int> g[N];

struct node{
	int l,r,num;
	i64 sum;
}t[N<<6];
int rt[N],idx;
#define mid (L+R>>1)
void upd(int &pos,int pre,int L,int R,int x){
	pos=++idx; t[pos]=t[pre]; 
	t[pos].sum+=x; t[pos].num++;
	if(L==R) return;
	if(x<=mid) upd(t[pos].l,t[pre].l,L,mid,x);
	else upd(t[pos].r,t[pre].r,mid+1,R,x);
}
int qry(int pos,int pos2,int pos3,int L,int R,i64 k){
	if(L==R) return t[pos].num+t[pos2].num-t[pos3].num*2-(k/L);
	i64 now=t[t[pos].l].sum+t[t[pos2].l].sum-t[t[pos3].l].sum*2;
	int num=t[t[pos].r].num+t[t[pos2].r].num-t[t[pos3].r].num*2;
	if(now<=k) return qry(t[pos].r,t[pos2].r,t[pos3].r,mid+1,R,k-now);
	return qry(t[pos].l,t[pos2].l,t[pos3].l,L,mid,k)+num;
}

int dep[N],top[N],siz[N],son[N],fa[N];
void dfs(int x,int y){
	dep[x]=dep[y]+1; fa[x]=y; siz[x]=1;
	for(auto e:f[x]){
		int u=e.first,id=e.second;
		if(u==y) continue;
		rt[u]=rt[x]; 
		for(int v:g[id]) upd(rt[u],rt[u],1,1e9,v);
		dfs(u,x); siz[x]+=siz[u];
		if(siz[u]>siz[son[x]]) son[x]=u;
	}
}
void dfs2(int x,int y){
	top[x]=y;
	if(son[x]) dfs2(son[x],y);
	for(auto e:f[x]){
		int u=e.first;
		if(!top[u]) dfs2(u,u);
	}
}
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
		else y=fa[top[y]];
	}
	return dep[x]<dep[y]?x:y;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>q;
	for(int x,y,i=1;i<n;++i) {
		cin>>x>>y;
		f[x].push_back({y,i});
		f[y].push_back({x,i});
	}
	for(int x,y,i=1;i<=m;++i) {
		cin>>x>>y;
		g[x].push_back(y);
	}
	dfs(1,0); dfs2(1,1);
	for(i64 s,t,x,y,i=1;i<=q;++i) {
		cin>>s>>t>>x>>y;
		int l=lca(s,t);
		cout<<max(-1ll,x-max(0,qry(rt[s],rt[t],rt[l],1,1e9,y)))<<'\n';
	}
	return 0;
}

希望这篇题解能够帮到你！

单纯的追求优秀的复杂度。
如果只是想做完这道题可以忽略本文。

前置知识：整体二分。

首先，这道题的经典做法是树上主席树，时间空间都是 $O(n \log n)$。

但事实上这道题可以使用整体二分做到 $O(n \log n)$ 的时间复杂度和 $O(n)$ 的空间复杂度。

整体二分的话还是常规思路，我们去枚举一个值 $mid$，即只在 $c_i \le mid$ 的时候使用银币。
如果想要做到 $O(n \log n)$ 的复杂度，那么复杂度应该是 $T(x) = 2T(\frac{x}{2}) + O(x)$，也就是链求和的部分要做到线性。
不能使用带 $\log$ 的数据结构维护，那么就考虑树上前缀和。

我们需要保证每次只对有用的点做前缀和。
所以容易想到虚树。

具体的，我们可以把所有费用在当前二分区间内的点拿出来建虚树。
同时，对于每个树链询问，都可以差分成 $O(1)$ 个树上前缀询问。
把这些点也放到虚树上。
分治的时候把点按照费用大小递归到两边即可。

实现细节的话，首先需要把所有的点按照 DFN 序排好，分裂的时候不打乱相对顺序以避免建虚树的时候排序。
另外，需要接一个 $O(1)$ LCA，使用单调栈建虚树。

常数很大，仅分析理论复杂度就好了。