BZOJ4009：[HNOI2015]接水果
? 解题记录 ? ? BZOJ ? ? 整体二分 ? ? 树状数组 ? ? 树链剖分 ?    2019-01-05 11:01:15    667    0    0

### 【输入样例】

```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。

## 假设原树为有根树，那么有两种情况。(下文中LCA指最近公共祖先)

1. lca(u,v)为u或v
2. lca(u,v)不为u且不为v

## 居然1A了，真的高兴qwq

```#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
struct edge {
int v, next;
} e[maxn << 1];
void adde(const int &u, const int &v) {
e[++cnt] = (edge) {v, head[u]};
}

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) {
}
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);
}
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;
}```

667 人读过

0 条评论