济南网站开发公司,做淘宝网站要求与想法,网页设计的尺寸大小是多少宽,个人导航页模板P3250 [HNOI2016]网络
给定一棵树#xff0c;有三种操作#xff1a;
给定u,v,wu, v, wu,v,w#xff0c;表示u,vu, vu,v路径上有一个重要度为www的请求#xff0c;给定ttt#xff0c;第ttt个发生的请求结束#xff0c;给定一个xxx#xff0c;假设xxx发生故障#xff0…P3250 [HNOI2016]网络
给定一棵树有三种操作
给定u,v,wu, v, wu,v,w表示u,vu, vu,v路径上有一个重要度为www的请求给定ttt第ttt个发生的请求结束给定一个xxx假设xxx发生故障未被影响的请求的最大重要度为多少如果没有请求则输出−1-1−1。
可以考虑二分答案如果大于等于midmidmid的请求都经过了这个点那么答案一定是小于midmidmid的
接下来问题转换为如何判断大于等于midmidmid的请求是否都经过了这个点可以考虑树上差分对区间整体修改
由于有多组询问如果每次单独judgejudgejudge复杂度将会是O(n2log2n)O(n ^ 2 \log ^ 2 n)O(n2log2n)的所以可以考虑整体二分做到复杂度是O(nlog2n)O(n \log ^ 2 n)O(nlog2n)的。
#include bits/stdc.husing namespace std;const int N 2e5 10;int head[N], to[N], nex[N], cnt 1;int son[N], sz[N], dep[N], fa[N], rk[N], id[N], top[N], tot;int sum[N], a[N], ans[N], n, m, num;int A[N], B[N], V[N];struct Res {int x, y, f, ff, v, id, type;
}q[N], q1[N], q2[N];inline int lowbit(int x) {return x (-x);
}void update(int x, int v) {while (x n) {sum[x] v;x lowbit(x);}
}int query(int x) {int ans 0;while (x) {ans sum[x];x - lowbit(x);}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, dep[rt] dep[f] 1, sz[rt] 1, rk[tot] rt, id[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[son[rt]] sz[to[i]]) {son[rt] to[i];}}
}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 x, int y) {while (top[x] ! top[y]) {if (dep[top[x]] dep[top[y]]) {swap(x, y);}x fa[top[x]];}return dep[x] dep[y] ? x : y;
}void solve(int l, int r, int L, int R) {if (L R || l r) {return ;}if (l r) {for (int i L; i R; i) {if (q[i].type 2) {ans[q[i].id] a[l];}}return ;}int mid l r 1, cnt1 0, cnt2 0, sum 0;for (int i L; i R; i) {if (q[i].type 1) {if (q[i].v a[mid]) {sum q[i].id;update(id[q[i].x], q[i].id), update(id[q[i].y], q[i].id), update(id[q[i].f], -q[i].id);if (q[i].ff) {update(id[q[i].ff], -q[i].id);}q2[cnt2] q[i];}else {q1[cnt1] q[i];}}else {int cur query(id[q[i].x] sz[q[i].x] - 1) - query(id[q[i].x] - 1);if (cur sum) {q1[cnt1] q[i];}else {q2[cnt2] q[i];}}}for (int i 1; i cnt2; i) {if (q2[i].type 1) {update(id[q2[i].x], -q2[i].id), update(id[q2[i].y], -q2[i].id), update(id[q2[i].f], q2[i].id);if (q2[i].ff) {update(id[q2[i].ff], q2[i].id);}}}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, mid, L, L cnt1 - 1), solve(mid 1, r, L cnt1, R);
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);scanf(%d %d, n, m);for (int i 1, x, y; i n; i) {scanf(%d %d, x, y);add(x, y);add(y, x);}dfs1(1, 0);dfs2(1, 1);for (int i 1, op, x; i m; i) {scanf(%d, op);if (op 0) {scanf(%d %d %d, A[i], B[i], V[i]);a[num] V[i];int u A[i], v B[i], f lca(u, v), ff fa[f];q[i] {u, v, f, ff, V[i], 1, 1};}else if (op 1) {scanf(%d, x);q[i] q[x];q[i].id -1;}else {scanf(%d, x);A[i] 0x3f3f3f3f;q[i] {x, 0, 0, 0, 0, i, 2};}}sort(a 1, a 1 num);num unique(a 1, a 1 num) - (a 1);a[0] -1;solve(0, num, 1, m);for (int i 1; i m; i) {if (A[i] 0x3f3f3f3f) {printf(%d\n, ans[i]);}}return 0;
}
