聚合影视网站建设,网络平台投诉电话,酷站海洛,自己网站建设清明梦超能力者黄YY
这题有点像【雨天的尾巴】【永无乡】的结合版本#xff0c;树上差分#xff0c;线段树合并#xff0c;权值线段树查找第kkk大。
对于操作iii#xff0c;我们可以对u−vu-vu−v路径上的点#xff0c;iii的权值加上111#xff0c;然后线段…清明梦超能力者黄YY
这题有点像【雨天的尾巴】【永无乡】的结合版本树上差分线段树合并权值线段树查找第kkk大。
对于操作iii我们可以对u−vu-vu−v路径上的点iii的权值加上111然后线段树合并查找第kkk大就好了。
#include bits/stdc.husing namespace std;const int N 1e5 10;int head[N], to[N 1], nex[N 1], cnt 1;int n, m, k, ans[N], root[N], value[N];int fa[N], top[N], dep[N], son[N], sz[N];int ls[N * 60], rs[N * 60], sum[N * 60], tot;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;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 push_up(int rt) {sum[rt] sum[ls[rt]] sum[rs[rt]];
}void update(int rt, int l, int r, int x, int value) {if (!rt) {rt tot;}if (l r) {sum[rt] value;return ;}int mid (l r) 1;if (x mid) {update(ls[rt], l, mid, x, value);}if (x mid) {update(rs[rt], mid 1, r, x, value);}push_up(rt);
}int merge(int x, int y, int l, int r) {if (x 0 || y 0) {return x | y;}if (l r) {sum[x] sum[y];return x;}int mid (l r) 1;ls[x] merge(ls[x], ls[y], l, mid);rs[x] merge(rs[x], rs[y], mid 1, r);push_up(x);return x;
}int find_k_th(int rt, int l, int r, int k) {if (l r) {return l;}int mid (l r) 1;if (k sum[ls[rt]]) {return find_k_th(rs[rt], mid 1, r, k - sum[ls[rt]]);}return find_k_th(ls[rt], l, mid, k);
}void dfs(int rt, int fa) {for (int i head[rt]; i; i nex[i]) {if (to[i] fa) {continue;}dfs(to[i], rt);root[rt] merge(root[rt], root[to[i]], 1, n);}if (k sum[root[rt]]) {ans[rt] find_k_th(root[rt], 1, n, sum[root[rt]] - k 1);}
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf(%d %d %d, n, m, k);for (int i 1; i n; i) {int x, y;scanf(%d %d, x, y);add(x, y);add(y, x);}dfs1(1, 0);dfs2(1, 1);for (int i 1; i m; i) {int u, v, c;scanf(%d %d %d, u, v, value[i]);int f lca(u, v), ff fa[f];update(root[u], 1, n, i, 1);update(root[v], 1, n, i, 1);update(root[f], 1, n, i, -1);if (ff) {update(root[ff], 1, n, i, -1);}}dfs(1, 0);for (int i 1; i n; i) {printf(%d%c, value[ans[i]], i n ? \n : );}return 0;
}异或树
异或操作容易想到拆位然后依次算贡献然后注意同一颗子树上相同的值如果出现了偶数次要相消线段树合并一下就好了。
#include bits/stdc.husing namespace std;typedef pairint, int pii;
typedef long long ll;const int N 1e5 10;int head[N], to[N 1], nex[N 1], cnt 1;int n, m, value[N], root[N];int ls[N * 33], rs[N * 33], sum[N * 33], num[N * 33][17], tot;ll ans[N];vectorpii ask[N];void push_up(int rt) {sum[rt] sum[ls[rt]] sum[rs[rt]];for (int i 0; i 16; i) {num[rt][i] num[ls[rt]][i] num[rs[rt]][i];}
}void update(int rt, int l, int r, int x) {if (!rt) {rt tot;}if (l r) {if (sum[rt]) {sum[rt] 0;for (int i 0; i 16; i) {num[rt][i] 0;}}else {sum[rt] 1;for (int i 0; i 16; i) {num[rt][i] x i 1;}}return ;}int mid l r 1;if (x mid) {update(ls[rt], l, mid, x);}else {update(rs[rt], mid 1, r, x);}push_up(rt);return ;
}int merge(int x, int y, int l, int r) {if (x 0 || y 0) {return x | y;}if (l r) {for (int i 0; i 16; i) {num[x][i] ^ num[y][i];}sum[x] ^ sum[y];return x;}int mid l r 1;ls[x] merge(ls[x], ls[y], l, mid);rs[x] merge(rs[x], rs[y], mid 1, r);push_up(x);return x;
}void add(int x, int y) {to[cnt] y;nex[cnt] head[x];head[x] cnt;
}ll query(int rt, int l, int r, int L, int R, int value) {if (!rt) {return 0;}if (l L r R) {ll ans 0;for (int i 0; i 16; i) {if (value i 1) {ans (1ll i) * (sum[rt] - num[rt][i]);}else {ans (1ll i) * num[rt][i];}}return ans;}int mid l r 1;ll ans 0;if (L mid) {ans query(ls[rt], l, mid, L, R, value);}if (R mid) {ans query(rs[rt], mid 1, r, L, R, value);}return ans;
}void dfs(int rt, int fa) {for (int i head[rt]; i; i nex[i]) {if (to[i] fa) {continue;}dfs(to[i], rt);root[rt] merge(root[rt], root[to[i]], 1, n);}update(root[rt], 1, n, value[rt]);for (auto it : ask[rt]) {if (it.second ! n) {ans[it.first] query(root[rt], 1, n, it.second 1, n, it.second);}}
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf(%d %d, n, m);for (int i 1; i n; i) {scanf(%d, value[i]);}for (int i 1; i n; i) {int x, y;scanf(%d %d, x, y);add(x, y);add(y, x);}for (int i 1; i m; i) {int u, x;scanf(%d %d, u, x);ask[u].push_back(make_pair(i, x));}dfs(1, 0);for (int i 1; i m; i) {printf(%lld\n, ans[i]);}return 0;
}
