模板下载网站源码,seo是搜索引擎优化,两学一做晋中市网站,个人主页制作B. Alyona and a tree#xff08;dsu on tree bit#xff09;
给定一颗以111号节点为根的树#xff0c;每个点有点权aia_iai#xff0c;边有边权#xff0c;如果vvv控制了点uuu#xff0c;当且仅当uuu是vvv的子树中的节点且dis(u,v)≤audis(u, v) \leq a_udis(u,v)≤…B. Alyona and a treedsu on tree bit
给定一颗以111号节点为根的树每个点有点权aia_iai边有边权如果vvv控制了点uuu当且仅当uuu是vvv的子树中的节点且dis(u,v)≤audis(u, v) \leq a_udis(u,v)≤au
我们定义d(u)d(u)d(u)为点111到点uuu距离则对于某个点vvv来说我们就是要在其字数上找d(u)−d(v)≤aud(u) - d(v) \leq a_ud(u)−d(v)≤aud(u)−au≤d(v)d(u) - a_u \leq d(v)d(u)−au≤d(v),
对所有的d(u)−au,d(u)d(u) - a_u, d(u)d(u)−au,d(u)进行离散化就可以考虑树上启发式合并 树状数组来完成上述操作整体复杂度O(nlognlogn)O (n \log n \log n)O(nlognlogn)。
#include bits/stdc.husing namespace std;const int N 2e5 10;int head[N], to[N], nex[N], value[N], cnt 1;int a[N], ans[N], sz[N], son[N], l[N], r[N], id[N], sum[N 3], tot, n, m;long long d[N], b[N 1];inline int lowbit(int x) {return x -x;
}void add(int x, int y, int w) {to[cnt] y;nex[cnt] head[x];value[cnt] w;head[x] cnt;
}void dfs(int rt, int fa) {sz[rt] 1, l[rt] tot, id[tot] rt;for (int i head[rt]; i; i nex[i]) {if (to[i] fa) {continue;}d[to[i]] d[rt] value[i];dfs(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 update(int x, int v) {while (x m) {sum[x] v;x lowbit(x);}
}int query(int x) {int ans 0;while (x) {ans sum[x];x - lowbit(x);}return ans;
}void dfs(int rt, int fa, bool keep) {for (int i head[rt]; i; i nex[i]) {if (to[i] fa || to[i] son[rt]) {continue;}dfs(to[i], rt, 0);}if (son[rt]) {dfs(son[rt], rt, 1);}for (int i head[rt]; i; i nex[i]) {if (to[i] fa || to[i] son[rt]) {continue;}for (int j l[to[i]]; j r[to[i]]; j) {update(d[id[j]], 1);}}ans[rt] query(a[rt]);update(d[rt], 1);if (!keep) {for (int i l[rt]; i r[rt]; i) {update(d[id[i]], -1);}}
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);scanf(%d, n);for (int i 1; i n; i) {scanf(%d, a[i]);}for (int i 2, x, w; i n; i) {scanf(%d %d, x, w);add(x, i, w);}dfs(1, 0);for (int i 1; i n; i) {b[m] d[i], b[m] d[i] - a[i];}sort(b 1, b 1 m);m unique(b 1, b 1 m) - (b 1);for (int i 1; i n; i) {int temp a[i];a[i] lower_bound(b 1, b 1 m, d[i]) - b;d[i] lower_bound(b 1, b 1 m, d[i] - temp) - b;}dfs(1, 0, 1);for (int i 1; i n; i) {printf(%d%c, ans[i], i n ? \n : );}return 0;
}
