rockdu
【题目描述】
风见幽香非常喜欢玩一个叫做 osu!的游戏，其中她最喜欢玩的模式就是接水果。
由于她已经DT FC 了The big black, 她觉得这个游戏太简单了，于是发明了一个更加难的版本。首先有一个地图，是一棵由 n 个顶点、n-1 条边组成的树（例如图 1给出的树包含 8 个顶点、7 条边）。这颗树上有 P 个盘子，每个盘子实际上是一条路径（例如图 1 中顶点 6 到顶点 8 的路径），并且每个盘子还有一个权值。第 i 个盘子就是顶点a_i到顶点b_i的路径(由于是树，所以从a_i到b_i的路径是唯一的)，权值为c_i。接下来依次会有Q个水果掉下来，每个水果本质上也是一条路径，第i 个水果是从顶点 u_i 到顶点v_i 的路径。幽香每次需要选择一个盘子去接当前的水果：一个盘子能接住一个水果，当且仅当盘子的路径是水果的路径的子路径（例如图1中从 3到7 的路径是从1到8的路径的子路径）。这里规定:从a 到b的路径与从b到 a的路径是同一条路径。当然为了提高难度，对于第 i 个水果，你需要选择能接住它的所有盘子中，权值第 k_i 小的那个盘子，每个盘子可重复使用（没有使用次数的上限：一个盘子接完一个水果后，后面还可继续接其他水果，只要它是水果路径的子路径）。幽香认为这个游戏很难，你能轻松解决给她看吗？
【输入】
第一行三个数 n和P 和Q，表示树的大小和盘子的个数和水果的个数。
接下来n-1 行，每行两个数 a、b，表示树上的a和b 之间有一条边。树中顶点按1到 n标号。
接下来 P 行，每行三个数 a、b、c，表示路径为 a 到 b、权值为 c 的盘子，其中0≤c≤10^9，a不等于b。
接下来Q行，每行三个数 u、v、k，表示路径为 u到 v的水果，其中 u不等于v，你需要选择第 k小的盘子，第k 小一定存在。
【输出】
对于每个果子，输出一行表示选择的盘子的权值。
【输入样例】
10 10 10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 3 2 217394434 10 7 13022269 6 7 283254485 6 8 333042360 4 6 442139372 8 3 225045590 10 4 922205209 10 8 808296330 9 2 486331361 4 9 551176338 1 8 5 3 8 3 3 8 4 1 8 3 4 8 1 2 3 1 2 3 1 2 3 1 2 4 1 1 4 1
【输出样例】
442139372 333042360 442139372 283254485 283254485 217394434 217394434 217394434 217394434 217394434
【提示】
N,P,Q≤40000。
一道经典的整体二分。
盘子能接到水果的条件是盘子是水果的子路径。
考虑一个盘子(u,v)可以接到哪些水果。
假设原树为有根树，那么有两种情况。(下文中LCA指最近公共祖先)
- lca(u,v)为u或v
- lca(u,v)不为u且不为v
对于第二种情况来说，相当于把水果的两个端点卡死在了u,v的子树内。
子树限制的问题就可以用dfs序。
为了方便我们规定一条路径用(x,y)表示，其中x的dfs序小于y。
这样相当于水果(x,y)种，x有一个取值范围，y有一个取值范围。
我们把盘子看成一个矩形，把水果看成一个点，那么被接到的条件等价于这个点落在矩形内。
问题就变成了对于每个点，求出覆盖它的权值第K大的矩形。
那么对于第一种情况怎么办呢？
现在已知(u,v)满足lca(u,v)=u (已经定义u的dfs序小于v)
设路径u->v上u之后的第一个点为t
我们发现只要满足一端在t的子树外，一端在v的子树内就可以了
为什么不是在u的子树外呢？画图可以发现，另一个端点在u的其它子树内其实也满足条件。
考虑我们规定了(u,v)的顺序，那么讨论一下u在t内还是v在t内就得到两个矩形。
这样落在其中任意一个就满足条件。
现在问题相当于对于每个点，求出覆盖它的权值第K大的图形(包括一个矩形、两个矩形)
这个就可以直接整体二分，二分一个权值，然后用扫描线加树状数组验证就行了。
整体二分写成扣除左边对右边的贡献比较好写。
居然1A了，真的高兴qwq
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
struct edge {
int v, next;
} e[maxn << 1];
int head[maxn], cnt;
void adde(const int &u, const int &v) {
e[++cnt] = (edge) {v, head[u]};
head[u] = cnt;
}
int dfn[maxn], dfned[maxn], dcnt, n, N, M, u, v, w;
int tp[maxn], fa[maxn], son[maxn], sz[maxn], dep[maxn];
void dfs(int u, int p) {
sz[u] = 1, fa[u] = p;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == p) continue;
dfs(v, u);
sz[u] += sz[v];
if(!son[u] || sz[son[u]] < sz[v])
son[u] = v;
}
}
void dfs2(int u, int top) {
dfn[u] = ++dcnt;
tp[u] = top, dep[u] = dep[fa[u]] + 1;
if(son[u]) dfs2(son[u], top);
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(v == fa[u] || v == son[u])
continue;
dfs2(v, v);
}
dfned[u] = dcnt;
}
int LCA(int u, int v) {
while(tp[u] != tp[v]) {
if(dep[tp[u]] < dep[tp[v]]) swap(u, v);
u = fa[tp[u]];
}
return dep[u] > dep[v] ? v : u;
}
int Fdown(int p, int u) {
while(tp[u] != tp[p]) {
if(fa[tp[u]] == p) return tp[u];
u = fa[tp[u]];
}
return son[p];
}
struct Fruit {int x, y, k, id;} frts[maxn], ftmp[maxn];
struct Rect {int l, r, d, u;};
struct Plate {
int t, w; Rect r1, r2;
bool operator < (const Plate &A) const {
return w < A.w;
}
} plts[maxn], ptmp[maxn];
struct Event {
int x, d, u, t;
bool operator < (const Event &A) const {
return x < A.x;
}
} ev[maxn << 1];
struct Query {
int x, y, id;
bool operator < (const Query &A) const {
return x < A.x;
}
} qs[maxn << 1];
int ans[maxn], tmp[maxn], ecnt, qcnt, ep;
namespace BIT {
int t[maxn];
#define lowbit(x) ((x) & (-(x)))
void add(int x, int dt) {
for(; x <= n; x += lowbit(x))
t[x] += dt;
}
void add(int l, int r, int dt) {
add(l, dt), add(r + 1, -dt);
}
int query(int x) {
int ans = 0;
for(; x; x -= lowbit(x))
ans += t[x];
return ans;
}
}
void solve(int pl, int pr, int fl, int fr, int L, int R) {
if(L >= R - 1) {
for(register int i = fl; i < fr; ++i)
ans[frts[i].id] = L;
return ;
}
if(fl == fr || pl == pr) return;
int mid = L + R >> 1;
int tmp, p1 = fl, p2 = fr - 1, p3 = pl, p4 = pr - 1;
ecnt = qcnt = 0, ep = 1;
for(register int i = fl; i < fr; ++i) {
qs[++qcnt] = (Query) {frts[i].x, frts[i].y, i};
}
for(register int i = pl; i < pr; ++i) {
if(plts[i].w < mid) {
ptmp[p3++] = plts[i];
ev[++ecnt] = (Event) {plts[i].r1.l, plts[i].r1.d, plts[i].r1.u, 1};
ev[++ecnt] = (Event) {plts[i].r1.r + 1, plts[i].r1.d, plts[i].r1.u, -1};
if(plts[i].t > 1) {
ev[++ecnt] = (Event) {plts[i].r2.l, plts[i].r2.d, plts[i].r2.u, 1};
ev[++ecnt] = (Event) {plts[i].r2.r + 1, plts[i].r2.d, plts[i].r2.u, -1};
}
} else {
ptmp[p4--] = plts[i];
}
}
sort(ev + 1, ev + ecnt + 1);
sort(qs + 1, qs + qcnt + 1);
for(register int i = 1; i <= qcnt; ++i) {
while(ep <= ecnt && ev[ep].x <= qs[i].x)
BIT::add(ev[ep].d, ev[ep].u, ev[ep].t), ++ep;
tmp = BIT::query(qs[i].y);
if(tmp < frts[qs[i].id].k)
frts[qs[i].id].k -= tmp, ftmp[p2--] = frts[qs[i].id];
else ftmp[p1++] = frts[qs[i].id];
}
for(register int i = fl; i < fr; ++i)
frts[i] = ftmp[i];
for(register int i = pl; i < pr; ++i)
plts[i] = ptmp[i];
while(ep <= ecnt) BIT::add(ev[ep].d, ev[ep].u, ev[ep].t), ++ep;
solve(pl, p3, fl, p1, L, mid);
solve(p3, pr, p1, fr, mid, R);
}
int main() {
scanf("%d%d%d", &n, &N, &M);
for(register int i = 1; i < n; ++i) {
scanf("%d%d", &u, &v);
adde(u, v), adde(v, u);
}
dfs(1, 0), dfs2(1, 1);
int lca;
for(register int i = 1; i <= N; ++i) {
scanf("%d%d%d", &u, &v, &w);
lca = LCA(u, v);
if(dfn[u] > dfn[v]) swap(u, v);
if(lca == u) {
lca = Fdown(u, v);
if(dfned[lca] == n) {
plts[i] = (Plate) {1, w,
(Rect) {1, dfn[lca] - 1, dfn[v], dfned[v]},
0, 0, 0, 0};
} else {
plts[i] = (Plate) {2, w,
(Rect) {1, dfn[lca] - 1, dfn[v], dfned[v]},
(Rect) {dfn[v], dfned[v], dfned[lca] + 1, n}};
}
} else {
plts[i] = (Plate) {1, w,
(Rect) {dfn[u], dfned[u], dfn[v], dfned[v]},
0, 0, 0, 0};
}
}
for(register int i = 1; i <= M; ++i) {
scanf("%d%d%d", &u, &v, &w);
if(dfn[u] > dfn[v]) swap(u, v);
frts[i] = (Fruit) {dfn[u], dfn[v], w, i};
}
sort(plts + 1, plts + N + 1);
solve(1, N + 1, 1, M + 1, 0, 1e9 + 1);
for(register int i = 1; i <= M; ++i)
printf("%d\n", ans[i]);
return 0;
}
没有帐号? 立即注册