正題

luogu 2146
金牌導航 樹鏈剖分-2

---

題目大意

有若干軟件，除了軟件0，所有軟件都依賴且只依賴于另外一個軟件

當要刪除一個軟件時，所有依賴于該軟件的軟件都要刪掉

當安裝一個軟件時，該軟件依賴的軟件都要安裝

問你每次操作會影響多少個軟件

---

解題思路

依賴連邊會形成一棵樹，

每次刪除搜索子樹，每次安裝搜索到根節點的路徑

到根節點的路徑用樹剖處理即可

---

代碼

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long #define N 100010 using namespace std; int n, x, w, q, tot; int v[N], fa[N], sz[N], ed[N], hs[N], anc[N], dep[N], head[N]; char str[100]; struct rec {int to, next; } a[N]; void add(int x, int y) {a[++tot].to = y;a[tot].next = head[x];head[x] = tot; } struct Tree { #define ls x * 2 #define rs x * 2 + 1int p[N << 2], s[N << 2], lazy[N << 2];void build(int x, int l, int r) {lazy[x] = -1;if (l == r)return;int mid = l + r >> 1;build(ls, l, mid);build(rs, mid + 1, r);return;}void up(int x) {s[x] = s[ls] + s[rs];return;}void down(int x, int l, int r) {if (lazy[x] != -1) {if (l < r) {int mid = l + r >> 1;lazy[ls] = lazy[rs] = lazy[x];s[ls] = lazy[x] * (mid - l + 1);s[rs] = lazy[x] * (r - mid);}lazy[x] = -1;}return;}void change(int x, int L, int R, int l, int r, int y) {if (L == l && R == r) {lazy[x] = y;s[x] = y * (r - l + 1);return;}down(x, L, R);int mid = L + R >> 1;if (r <= mid)change(ls, L, mid, l, r, y);else if (l > mid)change(rs, mid + 1, R, l, r, y);elsechange(ls, L, mid, l, mid, y), change(rs, mid + 1, R, mid + 1, r, y);up(x);}int ask(int x, int L, int R, int l, int r) {if (L == l && R == r)return s[x];down(x, L, R);int mid = L + R >> 1;if (r <= mid)return ask(ls, L, mid, l, r);else if (l > mid)return ask(rs, mid + 1, R, l, r);elsereturn ask(ls, L, mid, l, mid) + ask(rs, mid + 1, R, mid + 1, r);} } T; void dfs1(int x) {sz[x] = 1;for (int i = head[x]; i; i = a[i].next) {dep[a[i].to] = dep[x] + 1;fa[a[i].to] = x;dfs1(a[i].to);sz[x] += sz[a[i].to];if (sz[a[i].to] > sz[hs[x]])hs[x] = a[i].to;}return; } void dfs2(int x, int y) {anc[x] = y;v[x] = ++w;if (hs[x])dfs2(hs[x], y);for (int i = head[x]; i; i = a[i].next)if (a[i].to != hs[x])dfs2(a[i].to, a[i].to);ed[x] = w; } int solve(int x) {//到根節點的路徑int sum = 0;while (anc[x] != 1) {sum += dep[x] - dep[anc[x]] + 1 - T.ask(1, 1, n, v[anc[x]], v[x]);T.change(1, 1, n, v[anc[x]], v[x], 1);x = fa[anc[x]];}sum += dep[x] - dep[anc[x]] + 1 - T.ask(1, 1, n, v[anc[x]], v[x]);T.change(1, 1, n, v[anc[x]], v[x], 1);return sum; } int solve2(int x) {//子樹int sum = T.ask(1, 1, n, v[x], ed[x]);T.change(1, 1, n, v[x], ed[x], 0);return sum; } int main() {scanf("%d", &n);for (int i = 2; i <= n; ++i) {scanf("%d", &x);x++;add(x, i);}dfs1(1);dfs2(1, 1);scanf("%d", &q);while (q--) {scanf("%s%d", str + 1, &x);x++;if (str[1] == 'i')printf("%d\n", solve(x));elseprintf("%d\n", solve2(x));}return 0; }

總結

以上是生活随笔為你收集整理的【树链剖分】软件管理（luogu 2146/金牌导航 树链剖分-2）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。