# 树链刨分学习总结

## 【NOI2015】软件包管理器（ 题目 ）：

```
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 using namespace std;
6
7 const int N = 200010;
8
9 int n;
10 int tid[N], top[N], pos[N], tidnum;
11 int size1[N], fa[N], dep[N], son[N];
12 int h[N], nex[N * 2], num[N * 2], dqx;
13
14 struct Node
15 {
16     int l, r, sum, flag;
17     Node() {}
18 };
19
20 Node tree[N * 4];
21
22 void add(int a, int b)
23 {
24     num[dqx] = b;
25     nex[dqx] = h[a];
26     h[a] = dqx++;
27 }
28
29 void dfs1(int u, int father, int depth)
30 {
31     size1[u] = 1;
32     fa[u] = father;
33     dep[u] = depth + 1;
34     for (int i = h[u]; ~i; i = nex[i])
35     {
36         int j = num[i];
37         if (j == father) continue;
38         dfs1(j, u, depth + 1);
39         size1[u] += size1[j];
40         if (!son[u] || size1[j] > size1[son[u]]) son[u] = j;
41     }
42 }
43
44 void dfs2(int u, int tp)
45 {
46     tid[u] = ++tidnum;
47     pos[tid[u]] = u;
48     top[u] = tp;
49
50     if (!son[u]) return;
51
52     dfs2(son[u], tp);
53     for (int i = h[u]; ~i; i = nex[i])
54     {
55         int j = num[i];
56         if (j != son[u] && j != fa[u])
57         {
58             dfs2(j, j);
59         }
60     }
61 }
62
63 void build(int id, int l, int r)
64 {
65     tree[id].l = l;
66     tree[id].r = r;
67     tree[id].sum = 0;
68     tree[id].flag = -1;
69
70     if (l == r) return;
71     int mid = (l + r) >> 1;
72     build(id << 1, l, mid);
73     build(id << 1 | 1, mid + 1, r);
74 }
75
76 void pushdown(int q)
77 {
78     tree[q << 1].sum = (tree[q << 1].r - tree[q << 1].l + 1) * tree[q].flag;
79     tree[q << 1 | 1].sum = (tree[q << 1 | 1].r - tree[q << 1 | 1].l + 1) * tree[q].flag;
80     tree[q << 1].flag = tree[q << 1 | 1].flag = tree[q].flag;
81     tree[q].flag = -1;
82 }
83
84 int get(int q, int l, int r)
85 {
86     if (tree[q].r<l || tree[q].l>r) return 0;
87     if (tree[q].l >= l && tree[q].r <= r) return tree[q].sum;
88     if (~tree[q].flag) pushdown(q);
89     return get(q << 1, l, r) + get(q << 1 | 1, l, r);
90 }
91
92 void update(int q, int l, int r, int v)
93 {
94     if (tree[q].r<l || tree[q].l>r) return;
95     if (tree[q].l >= l && tree[q].r <= r)
96     {
97         tree[q].sum = (tree[q].r - tree[q].l + 1) * v;
98         tree[q].flag = v;
99         return;
100     }
101
102     if (~tree[q].flag) pushdown(q);
103     update(q << 1, l, r, v);
104     update(q << 1 | 1, l, r, v);
105     tree[q].sum = tree[q << 1].sum + tree[q << 1 | 1].sum;
106     return;
107 }
108
109 void change(int a, int b, int v)
110 {
111     while (top[a] != top[b])
112     {
113         if (dep[a] < dep[b]) swap(a, b);
114         update(1, tid[top[a]], tid[a], v);
115         a = fa[top[a]];
116     }
117
118     if (dep[a] > dep[b]) swap(a, b);
119     update(1, tid[a], tid[b], v);
120     return;
121 }
122
123 int main()
124 {
125     scanf("%d", &n);
126
127     memset(h, -1, sizeof(h));
128     for (int i = 2; i <= n; i++)
129     {
130         int a;
131         scanf("%d", &a);
132         a++;
134     }
135
136     dfs1(1, 1, 1);
137     dfs2(1, 1);
138
139     int q;
140     scanf("%d", &q);
141     build(1, 1, tidnum);
142     while (q--)
143     {
144         char s[20];
145         scanf("%s", s);
146
147         int x;
148         scanf("%d", &x);
149         x++;
150
151         int t1 = tree[1].sum;
152         if (s[0] == 'i')
153         {
154             change(1, x, 1);
155             int t2 = tree[1].sum;
156             printf("%d\n", abs(t1 - t2));
157         }
158         else
159         {
160             update(1, tid[x], tid[x] + size1[x] - 1, 0);
161             int t2 = tree[1].sum;
162             printf("%d\n", abs(t1 - t2));
163         }
164     }
165
166
167 }

View Code```