高端设计网站建设,wordpress 修订版本,丽水建设局网站文件,企业注册官网入口P3242 [HNOI2015] 接水果
给定一棵树#xff0c;定义给定了ppp个盘子#xff0c;每个盘子是树上u,vu, vu,v两点的路径#xff0c;且盘子有权值#xff0c;定义水果#xff0c;水果也是树上u,vu, vu,v两点间的路径。
有qqq个询问#xff0c;每次给定u,v,ku, v, ku,v,k定义给定了ppp个盘子每个盘子是树上u,vu, vu,v两点的路径且盘子有权值定义水果水果也是树上u,vu, vu,v两点间的路径。
有qqq个询问每次给定u,v,ku, v, ku,v,k表示可以接住水果u,vu, vu,v的盘子中权值第kkk小的权值是什么输出权值一个盘子可以接住一个水果当且仅当盘子是水果的子路径。
考虑如何求是否覆盖对每个点dfsdfsdfs序得到[sti,edi][st_i, ed_i][sti,edi]对于(u,v),stu≤stv(u, v), st_u \le st_v(u,v),stu≤stv
lca(u,v)ulca(u, v) ulca(u,v)u则只要有一个点dfsdfsdfs序在[stv,edv][st_v, ed_v][stv,edv]并且有一个点dfsdfsdfs序在[1,stz−1],[edz1,n][1, st_z - 1], [ed_z 1, n][1,stz−1],[edz1,n]即为内含其中zzz为u,vu, vu,v路径上uuu的儿子。lca(u,v)≠ulca(u, v) \ne ulca(u,v)u则只要有一个点dfsdfsdfs序在[stu,edu][st_u, ed_u][stu,edu]并且有一个点dfsdfsdfs序在[stv,edv][st_v, ed_v][stv,edv]即为内含。
可以把所有矩形的差分类似扫描线离线一下然后整体二分即可。
#include bits/stdc.husing namespace std;const int N 1e5 10;int head[N], to[N 1], nex[N 1], cnt 1;int son[N], dep[N], top[N], sz[N], st[N], ed[N], fa[N], tot;int ans[N], sum[N], n, P, Q, num;struct Res {int op, x, l, r, k, id;bool operator (const Res t) const {return x ! t.x ? x t.x : op t.op;}
}q[N * 5], q1[N * 5], q2[N * 5];inline int lowbit(int x) {return x (-x);
}void update(int rt, int v) {while (rt n) {sum[rt] v;rt lowbit(rt);}
}int query(int rt) {int ans 0;while (rt) {ans sum[rt];rt - lowbit(rt);}return ans;
}void add(int x, int y) {to[cnt] y;nex[cnt] head[x];head[x] cnt;
}void dfs1(int rt, int f) {fa[rt] f, sz[rt] 1, dep[rt] dep[f] 1, st[rt] tot;for (int i head[rt]; i; i nex[i]) {if (to[i] f) {continue;}dfs1(to[i], rt);sz[rt] sz[to[i]];if (!son[rt] || sz[to[i]] sz[son[rt]]) {son[rt] to[i];}}ed[rt] tot;
}void dfs2(int rt, int tp) {top[rt] tp;if (!son[rt]) {return ;}dfs2(son[rt], tp);for (int i head[rt]; i; i nex[i]) {if (to[i] fa[rt] || to[i] son[rt]) {continue;}dfs2(to[i], to[i]);}
}int lca(int u, int v) {while (top[u] ! top[v]) {if (dep[top[u]] dep[top[v]]) {swap(u, v);}u fa[top[u]];}return dep[u] dep[v] ? u : v;
}int get(int u, int v) {while (top[u] ! top[v]) {if (fa[top[v]] u) {return top[v];}v fa[top[v]];}return son[u];
}void solve(int L, int R, int l, int r) {if (L R) {return ;}if (l r) {for (int i L; i R; i) {if (q[i].op 2) {ans[q[i].id] l;}}return ;}int mid l r 1, cnt1 0, cnt2 0;for (int i L; i R; i) {if (q[i].op ! 2) {if (q[i].k mid) {update(q[i].l, q[i].op), update(q[i].r 1, -q[i].op);q1[cnt1] q[i];}else {q2[cnt2] q[i];}}else {int cur query(q[i].l);if (cur q[i].k) {q1[cnt1] q[i];}else {q[i].k - cur;q2[cnt2] q[i];}}}for (int i 1; i cnt1; i) {if (q1[i].op ! 2) {update(q1[i].l, -q1[i].op), update(q1[i].r 1, q1[i].op);}}for (int i 1; i cnt1; i) {q[L i - 1] q1[i];}for (int i 1; i cnt2; i) {q[L cnt1 i - 1] q2[i];}solve(L, L cnt1 - 1, l, mid), solve(L cnt1, R, mid 1, r);
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);scanf(%d %d %d, n, P, Q);for (int i 1, u, v; i n; i) {scanf(%d %d, u, v);add(u, v);add(v, u);}dfs1(1, 0);dfs2(1, 1);for (int i 1, u, v, x; i P; i) {scanf(%d %d %d, u, v, x);if (st[u] st[v]) {swap(u, v);}// u v;int cur lca(u, v);if (cur u) {int z get(u, v);// [1, st[z] - 1]if (st[z] ! 1) {q[num] {1, 1, st[v], ed[v], x, 0};q[num] {-1, st[z], st[v], ed[v], x, 0};}// [ed[z] 1, n]if (ed[z] ! n) {q[num] {1, st[v], ed[z] 1, n, x, 0};q[num] {-1, ed[v] 1, ed[z] 1, n, x, 0};}}else {q[num] {1, st[u], st[v], ed[v], x, 0};q[num] {-1, ed[u] 1, st[v], ed[v], x, 0};}}for (int i 1, u, v, k; i Q; i) {scanf(%d %d %d, u, v, k);if (st[u] st[v]) {swap(u, v);}q[num] {2, st[u], st[v], 0, k, i};}sort(q 1, q 1 num);solve(1, num, 0, 1000000000);for (int i 1; i Q; i) {printf(%d\n, ans[i]);}return 0;
}
