E. Party Company

容易發(fā)現(xiàn)這是一顆樹(shù)形結(jié)構(gòu)，根節(jié)點(diǎn)為$1$，并且有點(diǎn)權(quán)從根節(jié)點(diǎn)開(kāi)始遞減。

題目大意就是給定一個(gè)點(diǎn)$u,l,r$，對(duì)于于$u$在同一個(gè)連通塊里，并且點(diǎn)權(quán)是在$[l,r]$之間的點(diǎn)答案貢獻(xiàn)加一。

如果理解到上述的題意，那這題就變得簡(jiǎn)單了。

由于我們要求的是在同一個(gè)聯(lián)通塊里的，并且點(diǎn)權(quán)具有單調(diào)性，我們可以通過(guò)二分跳轉(zhuǎn)到可以滿足的深度最小的節(jié)點(diǎn)上去，在這個(gè)節(jié)點(diǎn)依附上$l$。

容易想到，滿足要求的點(diǎn)一定是出現(xiàn)在這個(gè)節(jié)點(diǎn)的子樹(shù)上的，所以我們可以動(dòng)態(tài)維護(hù)一個(gè)以$l$的有序數(shù)組，然后在每個(gè)節(jié)點(diǎn)二分查找，有多少個(gè)值是小于等于當(dāng)前節(jié)點(diǎn)的，這個(gè)值就是當(dāng)前節(jié)點(diǎn)的答案了。

當(dāng)我們退出這顆子樹(shù)的時(shí)候，記得清空這個(gè)節(jié)點(diǎn)上依附的$l$。

由于$l,r$都比較小，所以可以直接通過(guò)樹(shù)狀數(shù)組，進(jìn)行單點(diǎn)修改，前綴和查詢，整體復(fù)雜度$O(n\log m+m\log m)$。

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int head[N], to[N], nex[N], cnt = 1;int fa[N], son[N], sz[N], top[N], rk[N], id[N], dep[N], tot;int n, m, value[N], ans[N];vector<int> vt[N];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, sz[rt] = 1, dep[rt] = dep[f] + 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[to[i]] > sz[son[rt]]) {son[rt] = to[i];}} }void dfs2(int rt, int tp) {top[rt] = tp, rk[++tot] = rt, id[rt] = tot;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]);} }void solve(int cur, int L, int R) {while (cur != 1) {if (fa[top[cur]] && value[fa[top[cur]]] <= R) {cur = fa[top[cur]];}else {int l = id[top[cur]], r = id[cur];while (l < r) {int mid = l + r >> 1;if (value[rk[mid]] > R) {l = mid + 1;}else {r = mid;}}vt[rk[l]].push_back(L);return ;}}vt[1].push_back(L); }int tree[N];int lowbit(int x) {return x & (-x); }void update(int x, int value) {while (x < N) {tree[x] += value;x += lowbit(x);} }int query(int x) {int ans = 0;while (x) {ans += tree[x];x -= lowbit(x);}return ans; }void dfs(int rt, int fa) {for (auto it : vt[rt]) {update(it, 1);}ans[rt] = query(value[rt]);for (int i = head[rt]; i; i = nex[i]) {if (to[i] == fa) {continue;}dfs(to[i], rt);}for (auto it : vt[rt]) {update(it, -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", &n, &m);for (int i = 1, fa; i <= n; i++) {scanf("%d %d", &value[i], &fa);if (i != 1) {add(fa, i);}}dfs1(1, 0);dfs2(1, 1);for (int i = 1; i <= m; i++) {int cur, l, r;scanf("%d %d %d", &cur, &l, &r);solve(cur, l, r);}dfs(1, 0);for (int i = 1; i <= n; i++) {printf("%d%c", ans[i], i == n ? '\n' : ' ');}return 0; }

總結(jié)

以上是生活随笔為你收集整理的E. Party Company（树上问题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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