BZOJ 4009 接水果

发表于 | 更新于

Link

Solution

在树上画一画，可以发现路径覆盖的充分必要条件。 二维条件，转化成寻找覆盖一个点的权值第KK大矩阵的问题。 用整体二分实现

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include "lucida"
import swap;
import sort;
import copy;
import fill;
const int MAXN=40000+11,MAXLOG=17;
int log_2[MAXN];
struct _{_() {
	log_2[0]=-1;
	for(int i=1;i<MAXN;++i) {
		log_2[i]=log_2[i>>1]+1;
	}
}}Auto;
int Ans[MAXN];
struct Edge {
	int to;Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
	G[t]=new Edge(f,G[t]);
}
struct Matrix {
	int x1,x2,y1,y2,c;
	Matrix() {}
	Matrix(int x1,int x2,int y1,int y2,int c):x1(x1),x2(x2),y1(y1),y2(y2),c(c) {}
	friend bool operator <(const Matrix &a,const Matrix &b) {
		return a.c<b.c;
	}
	void Adjust() {
		if(x1>y1) {
			swap(x1,y1);
			swap(x2,y2);
		}
		if(!(x2<y1)) {
			throw;
		}
	}
}mtx[MAXN<<1];int mc;
struct Query {
	int x,y,K,id;
	friend bool operator <(const Query &a,const Query &b) {
		return a.x<b.x;
	}
}q[MAXN];
//盘子是矩形 水果是点 对于每个点 需要知道覆盖它的权值第K大的矩形!
//合法的矩形 [x1,x2] & [y1,y2] = () ! 只要让[x1,x2]都小就可以了！！
int par[MAXN][MAXLOG],fa[MAXN],dfs[MAXN],lbd[MAXN],rbd[MAXN],dc,dep[MAXN]={0,1};
void DFS(int pos) {
	par[pos][0]=fa[pos];
	for(int lg=1;lg<=log_2[dep[pos]];++lg) {
		par[pos][lg]=par[par[pos][lg-1]][lg-1];
	}
	dfs[lbd[pos]=++dc]=pos;
	for(Edge *e=G[pos];e;e=e->pre) if(e->to!=fa[pos]) {
		int u=e->to;
		fa[u]=pos;
		dep[u]=dep[pos]+1;
		DFS(u);
	}
	rbd[pos]=dc;
}
int Jump(int pos,int len) {
	for(int lg=log_2[len];~lg;--lg) if(len>>lg&1) {
		pos=par[pos][lg];
	}
	return pos;
}
int LCA(int p1,int p2) {
	if(dep[p1]<dep[p2]) {
		swap(p1,p2);
	}
	p1=Jump(p1,dep[p1]-dep[p2]);
	if(p1!=p2) {
		for(int lg=log_2[dep[p1]-1];~lg;--lg) if(par[p1][lg]!=par[p2][lg]) {  // -  1 ?
			p1=par[p1][lg];p2=par[p2][lg];
		}
		p1=fa[p1];
	}
	return p1;
}

void Deal(int x,int y,int c) {
	if(lbd[x]>lbd[y]) {
		swap(x,y);
	}
	int lca=LCA(x,y);
	if(x==lca) {
		int sec=Jump(y,dep[y]-dep[x]-1);
		if(1<=lbd[sec]-1) {
			mtx[++mc]=Matrix(1,lbd[sec]-1,lbd[y],rbd[y],c);
		}
		if(rbd[sec]+1<=dc) {
			mtx[++mc]=Matrix(rbd[sec]+1,dc,lbd[y],rbd[y],c);
		}
	} else {
		mtx[++mc]=Matrix(lbd[x],rbd[x],lbd[y],rbd[y],c);
	}
}
struct Bit {
	int n,us[MAXN],ut,a[MAXN];
	Bit() {}
	Bit(int n):n(n),ut(0) {
		fill(us+1,us+1+n,0);
	}
	void Reset() {
		++ut;
	}
	void Add(int pos,int v) {
		for(;pos<=n;pos+=pos & -pos) {
			(a[pos]=us[pos]==ut?a[pos]:(us[pos]=ut,0))+=v;
		}
	}
	void Add(int l,int r,int v) {
		Add(l,v);
		Add(r+1,-v);
	}
	int At(int pos) {
		int res=0;
		for(;pos;pos-=pos & -pos) {
			res+=(a[pos]=us[pos]==ut?a[pos]:(us[pos]=ut,0));
		}
		return res;
	}
};
struct Scan {
	int x,y1,y2;
	bool isLeft;
	Scan() {}
	Scan(int x,int y1,int y2,bool isLeft):x(x),y1(y1),y2(y2),isLeft(isLeft) {}
	friend bool operator <(const Scan &a,const Scan &b) {
		return a.x!=b.x?a.x<b.x:!a.isLeft;
	}
};
//这次不能再重写了！！
void DC(int ml,int mr,int ql,int qr) {//在矩阵[ml,mr]的区间里面，查找询问[ql,qr]的答案.
//需要知道[ql,qr]的每个点，被[ml,mr]的矩阵覆盖了多少次.扫描线?
	static Bit bit(dc);
	static Scan scan[MAXN<<2];
	static Query t[MAXN];
	if(ml==mr) {
		for(int i=ql;i<=qr;++i) {
			Ans[q[i].id]=mtx[ml].c;
		}
	} else {
		int sc=0,mmid=(ml+mr)>>1;
		for(int i=ml;i<=mmid;++i) {
			scan[++sc]=Scan(mtx[i].x1,mtx[i].y1,mtx[i].y2,1);
			scan[++sc]=Scan(mtx[i].x2+1,mtx[i].y1,mtx[i].y2,0);
		}
		sort(scan+1,scan+1+sc);
		sort(q+ql,q+qr+1);
		bit.Reset();
		int tl=ql,tr=qr;
		for(int i=ql,sp=1;i<=qr;++i) {
			while(sp<=sc && scan[sp].x<=q[i].x) {
				bit.Add(scan[sp].y1,scan[sp].y2,scan[sp].isLeft?1:-1);		
				sp++;
			}
			int sum=bit.At(q[i].y);
			if(q[i].K<=sum) {
				t[tl++]=q[i];
			} else {
				q[i].K-=sum;
				t[tr--]=q[i];
			}
		}
		copy(t+ql,t+qr+1,q+ql);
		DC(ml,mmid,ql,tl-1);
		DC(mmid+1,mr,tr+1,qr);
	}
}
int main() {
//	freopen("input","r",stdin);
	int n,disc,qc;
	is>>n>>disc>>qc;
	for(int i=1;i<=n-1;++i) {
		int x,y;is>>x>>y;
		Adde(x,y);
	}
	DFS(1);
	for(int i=1;i<=disc;++i) {
		int x,y,c;is>>x>>y>>c;
		Deal(x,y,c);
	}
	for(int i=1;i<=mc;++i) {
		mtx[i].Adjust();
	}
	sort(mtx+1,mtx+1+mc);
	for(int i=1;i<=qc;++i) {
		is>>q[i].x>>q[i].y>>q[i].K;
		q[i].id=i;
		if((q[i].x=lbd[q[i].x])>(q[i].y=lbd[q[i].y])) {
			swap(q[i].x,q[i].y);
		}
	}
	sort(q+1,q+1+qc);
	DC(1,mc,1,qc);
	for(int i=1;i<=qc;++i) {
		os<<Ans[i]<<'\n';
	}
	return 0;
}