广州最新重大新闻,windows优化软件哪个好,电脑网页开发,网站怎么申请微博登录P4175 [CTSC2008]网络管理
给定一棵有nnn个节点的树#xff0c;点有点权#xff0c;有两种操作#xff1a;① 修改某个点的点权#xff0c;② 查询两点路径间的点权第kkk大。
给定u,vu, vu,v#xff0c;选定111号节点为根节点#xff0c;设inf(x)inf(x)inf(x)表示从根节…P4175 [CTSC2008]网络管理
给定一棵有nnn个节点的树点有点权有两种操作① 修改某个点的点权② 查询两点路径间的点权第kkk大。
给定u,vu, vu,v选定111号节点为根节点设inf(x)inf(x)inf(x)表示从根节点到点xxx的信息两点间的信息可以描述为inf(u)inf(v)−inf(lca(u,v))−fa(inf(lca(u,v)))inf(u) inf(v) - inf(lca(u, v)) - fa(inf(lca(u, v)))inf(u)inf(v)−inf(lca(u,v))−fa(inf(lca(u,v)))
由此我们可以把树上每个点拆成[l,r,x][l, r, x][l,r,x]lll为这个点进入dfsdfsdfs的dfsdfsdfs序rrr为这个点走出dfsdfsdfs的dfsdfsdfs序
我们要查找inf(u)inf(u)inf(u)上的信息就只要查找有多少个[l,r,x][l, r, x][l,r,x]满足l≤dfn(u)≤rl \leq dfn(u) \leq rl≤dfn(u)≤r树状数组区间更新单点查询就好了。
对于每个询问可以写成u,v,lca(u,v),fa(lca(u,v))u, v, lca(u, v), fa(lca(u, v))u,v,lca(u,v),fa(lca(u,v))我们把树上的点修改操作询问操作放到数组中整体二分一下即可。
感觉代码好像比树套树好写一点点……
#include bits/stdc.husing namespace std;const int N 2e5 10;int head[N], to[N], nex[N], cnt 1;int a[N], ans[N], n, m;int son[N], fa[N], l[N], dep[N], r[N], sz[N], top[N], sum[N], tot;struct Res {int l, r, f, ff, x, id, type;
}q[N], q1[N], q2[N];void add(int x, int y) {to[cnt] y;nex[cnt] head[x];head[x] cnt;
}void dfs1(int rt, int f) {dep[rt] dep[f] 1, fa[rt] f, sz[rt] 1, l[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];}}r[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 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;
}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 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] l;}}return ;}int mid l r 1, cnt1 0, cnt2 0;for (int i L; i R; i) {if (q[i].type 1) {if (q[i].x mid) {int l q[i].l, r q[i].r;update(l, q[i].id), update(r 1, -q[i].id);q1[cnt1] q[i];}else {q2[cnt2] q[i];}}else {int cur query(q[i].l) query(q[i].r) - query(q[i].f) - query(q[i].ff);if (cur q[i].x) {q1[cnt1] q[i];}else {q[i].x - cur;q2[cnt2] q[i];}}}for (int i 1; i cnt1; i) {if (q1[i].type 1) {int l q1[i].l, r q1[i].r;update(l, -q1[i].id), update(r 1, q1[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; i n; i) {scanf(%d, a[i]);}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; i m; i) {ans[i] 1000000000;}int num 0;for (int i 1; i n; i) {q[num] {l[i], r[i], 0, 0, a[i], 1, 1};}for (int i 1, k, x, y; i m; i) {scanf(%d %d %d, k, x, y);if (!k) {q[num] {l[x], r[x], 0, 0, a[x], -1, 1};a[x] y;q[num] {l[x], r[x], 0, 0, a[x], 1, 1};}else {int f lca(x, y), ff fa[f], sum dep[x] dep[y] - dep[f] - dep[ff];if (sum k) {q[num] {l[x], l[y], l[f], l[ff], sum - k 1, i, 2};}else {ans[i] -1;}}}solve(0, 100000000, 1, num);for (int i 1; i m; i) {if (ans[i] ! 1000000000) {if (ans[i] -1) {puts(invalid request!);}else {printf(%d\n, ans[i]);}}}return 0;
}
