HNOI2015 接水果 题解

思路

这道题是一道整体二分 + 扫描线 + 树链剖分（其实是 DFS 序） 的综合题

首先，遇到这种“一条路径是另一条路径的子路径”问题，我们第一反应肯定是懵的。树上路径怎么比大小？怎么求第 k 小？这玩意看着就像个二维偏序，但路径它不是直的。

正男则反 （强行套用），我们不去想水果怎么匹配盘子，而是想：一个盘子路径能接住哪些水果路径？

这里有一个极其关键的转化：利用 DFS 序把子树转化成区间 。

对于一条路径 $(a,b)$，设 $l = \text{lca}(a,b)$。

我们先假设 $a$ 和 $b$ 不是祖先关系（也就是 $l \neq a$ 且 $l \neq b$）。

那么，如果一个水果路径 $(u,v)$ 要包含这个盘子 $(a,b)$，$u$ 必须落在 $a$ 的子树里，$v$ 必须落在 $b$ 的子树里（或者反过来，但因为我们只关心无序路径，所以把两边端点匹配好）。

转化成 DFS 序就是：

  • $dfn[u] \in [dfn[a], dfn[a]+siz[a]-1]$
  • $dfn[v] \in [dfn[b], dfn[b]+siz[b]-1]$

你看，一个盘子就变成了一个矩形 ！横坐标是 $a$ 的子树区间，纵坐标是 $b$ 的子树区间。

主播主播，那如果 $a$ 是 $b$ 的祖先呢？

这十分地白痴，但我实际中确实被这个卡了。

如果 $a$ 是 $b$ 的祖先（假设 $a$ 在上），那么盘子路径是 $a \to b$。水果要包含它，一端（假设是 $u$）必须在 $b$ 的子树里，但另一端 $v$ 不能在 $a$ 的子树里随变选——因为如果 $v$ 也选在 $a$ 的子树里的某个分支，路径会变短，包含不了整条 $a \to b$。

实际上，$v$ 必须选在 $a$ 子树挖掉 $a$ 到 $b$ 路径上第一个儿子 $c$ 的子树 之外的部分。

所以这就会拆成两个矩形 ：

  1. $[dfn[b], dfn[b]+siz[b]-1] \times [1, dfn[c]-1]$
  2. $[dfn[b], dfn[b]+siz[b]-1] \times [dfn[c]+siz[c], n]$

（记得把两个维度都填满，因为是无序的，所以横纵坐标要对称，或者统一把 $dfn$ 小的放前面，防止重复计算。）

那现在问题就简单了：

  • 盘子 $\longrightarrow$ 带权值的矩形（权值就是 $c_i$）
  • 水果 $\longrightarrow$ 一个点 $(dfn[u], dfn[v])$

我们要回答的是：覆盖这个点的所有矩形中，权值第 $k$ 小的那个是多少？

这就是一个经典的整体二分 + 二维数点 问题。

我们二分答案权值 $mid$，把权值 $\le mid$ 的盘子（矩形）加入扫描线（树状数组维护差分），然后对于每个水果（点），查询这个点被多少个矩形覆盖。如果覆盖数 $\ge k$，说明答案在左区间；否则 $k$ 减去覆盖数，去右区间。

整体二分的时间复杂度是 $O((p+q) \log^2 n)$，因为每次扫描线要 $\log n$，整体二分要 $\log V$。
接水果这道题最难的地方是把路径转化成矩形的分类讨论

Code

非常的丑陋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>

using namespace std;
int n,p,q,dfn[40010],dep[40010],siz[40010],ba[40010][17],dfntot;
vector<int>e[40010];
int li[200010],lcnt,rt[200010];
inline void dfs(int u){
	for(int i=1;i<17;i++)ba[u][i]=ba[ba[u][i-1]][i-1];
	dfn[u]=++dfntot;
	siz[u]=1;
	for(auto v:e[u]){
		if(v==ba[u][0])continue;
		ba[v][0]=u;
		dep[v]=dep[u]+1;
		dfs(v);
		siz[u]+=siz[v];
	}
}
inline int lca(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=16;i>=0;i--)if(dep[u]-dep[v]-1>=(1<<i))u=ba[u][i];
	if(ba[u][0]==v)return u;
	u=ba[u][0];
	for(int i=16;i>=0;i--)if(ba[u][i]!=ba[v][i])u=ba[u][i],v=ba[v][i];
	return u;
}
inline int lowbit(int x){
	return x&-x;
}
int sum[10000010],tot,ls[10000010],rs[10000010];
inline void change(int &k,int l,int r,int pos,int val){
	if(!k)k=++tot;
	sum[k]+=val;
	if(l==r)return;
	int mid(l+r>>1);
	if(pos<=mid)change(ls[k],l,mid,pos,val);
	else change(rs[k],mid+1,r,pos,val);
}
int bb[40010],bcnt;
inline int query(int l,int r,int val){
	if(l==r)return l;
	int t=0;
	for(int i=1;i<=bcnt;i++)t+=sum[ls[bb[i]]];
	int mid(l+r>>1);
	if(val<=t){
		for(int i=1;i<=bcnt;i++)bb[i]=ls[bb[i]];
		return query(l,mid,val);
	}
	for(int i=1;i<=bcnt;i++)bb[i]=rs[bb[i]];
	return query(mid+1,r,val-t);
}
inline void modify(int l,int r,int val,int z){
	for(int i=l;i<=n;i+=lowbit(i))change(rt[i],1,lcnt,val,z);
	for(int i=r+1;i<=n;i+=lowbit(i))change(rt[i],1,lcnt,val,-z);
}
inline int ask(int l,int r){
	bcnt=0;
	for(int i=l;i>=1;i-=lowbit(i))bb[++bcnt]=rt[i];
	return query(1,lcnt,r);
}
struct no{
	int typ,x,l,r,a,id;
}que[300010];
int qcnt,ans[200010];
inline void cutup(int x1,int y1,int x2,int y2,int w){
	if(x1>x2 or y1>y2)return;
	que[++qcnt]={2,x2,y1,y2,w};
	que[++qcnt]={0,x1,y1,y2,w};
	que[++qcnt]={0,y1,x1,x2,w};
	que[++qcnt]={2,y2,x1,x2,w};
}
int t1[40010],t2[40010],t3[40010];
main(){
	cin.tie(0)->ios::sync_with_stdio(0);
	cin>>n>>p>>q;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1);
	for(int i=1;i<=p;i++){
		int a,b,c;
		cin>>a>>b>>c;
		t1[i]=a,t2[i]=b,t3[i]=c;
		li[++lcnt]=c;
	}
	sort(1+li,1+li+lcnt);
	lcnt=unique(1+li,1+li+lcnt)-li-1;
	for(int i=1;i<=p;i++){
		int a=t1[i],b=t2[i],c=lower_bound(1+li,1+li+lcnt,t3[i])-li;
		if(dep[a]>dep[b])swap(a,b);
		if(dfn[a]+siz[a]-1>=dfn[b] and dfn[a]<=dfn[b]){
			int x=lca(a,b);
			//cout<<1<<' '<<dfn[x]-1<<' '<<dfn[b]<<' '<<dfn[b]+siz[b]-1<<'\n';
			cutup(1,dfn[b],dfn[x]-1,dfn[b]+siz[b]-1,c);
			cutup(dfn[x]+siz[x],dfn[b],n,dfn[b]+siz[b]-1,c);
		}else cutup(dfn[a],dfn[b],dfn[a]+siz[a]-1,dfn[b]+siz[b]-1,c);
	}
	for(int i=1;i<=q;i++){
		int u,v,k;
		cin>>u>>v>>k;
		que[++qcnt]={1,dfn[u],dfn[v],dfn[v],k,i};
	}
	sort(1+que,1+que+qcnt,[&](no x,no y){
		if(x.x==y.x)return x.typ<y.typ;
		return x.x<y.x;
	});
	for(int i=1;i<=qcnt;i++){
		if(que[i].typ==0)modify(que[i].l,que[i].r,que[i].a,1);
		if(que[i].typ==1)ans[que[i].id]=ask(que[i].l,que[i].a);
		if(que[i].typ==2)modify(que[i].l,que[i].r,que[i].a,-1);
	}
	for(int i=1;i<=q;i++)cout<<li[ans[i]]<<'\n';
	return 0;
}
#题解
HNOI2015 接水果 题解
https://zxtweb.fun/posts/cnb-21222541/
作者
站长
发布于
2026年7月7日
许可协议