B. Alyona and a tree（dsu on tree + bit）

給定一顆以$1$號節(jié)點為根的樹，每個點有點權(quán)$a_i$，邊有邊權(quán)，如果$v$控制了點$u$，當且僅當$u$是$v$的子樹中的節(jié)點且$dis(u,v)\le a_u$，

我們定義$d(u)$為點$1$到點$u$距離，則對于某個點$v$來說我們就是要在其字數(shù)上找$d(u)?d(v)\le a_u$，$d(u)?a_u\le d(v)$,

對所有的$d(u)?a_u,d(u)$進行離散化，就可以考慮樹上啟發(fā)式合并 + 樹狀數(shù)組來完成上述操作，整體復雜度$O(n\log n\log n)$。

#include <bits/stdc++.h>using 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; }

總結(jié)

以上是生活随笔為你收集整理的B. Alyona and a tree（dsu on tree + bit）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。