树链刨分学习总结

概念:

对于一棵有根树,每个非叶节点选择至多一个连向孩子的边称为 “实边”(重边) ,这个边集称为这棵树的一个链剖分,不在集合中的边称为“虚边“(轻边)。如图,黑边为重边,白边为轻边。

重链:

每个非叶节点向他的节点数最大的子节点连一条重边;

重链求LCA:

如果两个点在同一条链上,则深度小的为答案。否则让较深的点爬到他所在的这条重链的最高点的父亲。

重链DFS序列:

当初始化每个节点的子节点数后(第一次DFS),再进行一次DFS,这一次DFS当递归到某一节点时,给他赋值一个下标,之后先递归他的子节点数最多的子节点,再递归其他子节点,这样就能让任意一条重链对应一个连续的区间。

【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++;
133         add(a, i);
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
我来评几句
登录后评论

已发表评论数()

相关站点

热门文章