树的序列化 - 学习笔记

树的序列化可以有很多种类：可以变成 dfs 序，可以变成欧拉序，还有什么括号序的科技。

但是除了第一个以外其他的都没什么用（要么也可以被已有的算法给替代掉）。所以表面上是讲树的序列化，实际上还是讲的 dfs 序的运用（dfs 序的基础知识没什么，但是其运用可以变得相当毒瘤）。

Q：为什么要把树序列化呢？

A：因为有些时候直接在树上面做可能会很复杂，甚至很难做，这是因为树的结构过于错综复杂了。如果把树变成一个简单的序列，那么线性 dp、区间 dp 等在树上不能搞的东西都可以搞了。

dfs 序

dfs 序，顾名思义就是 dfs 的顺序，更加具体的来说，就是在树上 dfs 搜索到的结点顺序（显然如果不加任何约束条件的话 dfs 序不唯一，因为这和搜索的顺序有关）。如果不会 dfs 的话左转出门。

假若我们有这样的一棵树。很容易根据 dfs 将其标号：

把每一个 dfs 序对应的结点记录下来，就会得到一个数组： { 1 , 3 , 5 , 6 , 2 , 4 } \{1,3,5,6,2,4\} {1,3,5,6,2,4}。注意是 dfs 对应的结点，而不是每一个结点对应的 dfs 序，它们俩是顺序不同的！

于是 dfs 序的定义就被讲完了，很简单是不是！（？

实际上 dfs 序的一个运用我们早就见过了：tarjan 全家桶。

时间戳

为什么我一定要强调这是顺序对应结点呢？这是因为 dfs 序是由两个东西构成的，一个是正宗的 dfs 序，一个是时间戳。

时间戳的定义貌似只可意会不可言传，具体是这么一个东西：

对于每一个结点，dfs 刚遍历到这个结点时，把这个点加入到时间戳的数组末尾的位置；要回溯的时候，也要把这个点加入到时间戳的数组末尾的位置。

还是沿用上面的树，很容易地出来时间戳： { 1 , 3 , 5 , 5 , 6 , 6 , 3 , 2 , 4 , 4 , 2 , 1 } \{1,3,5,5,6,6,3,2,4,4,2,1\} {1,3,5,5,6,6,3,2,4,4,2,1}。也就是每一个点刚被递归到的时候加一遍，回溯的时候也加一遍。

那么它有着怎样的性质呢？

对于每一个结点 $u$ 为根的子树，这个子树在序列中会对应一个区间，且这个区间一定是 $[u刚被遍历到的时候加入数组的位置,u回溯的时候加入数组的位置]$。

这个性质有一些显然，因为一个点子树里面的所有点进入一定比这个点进入的晚，出来一定比这个点出来的早，所以就构成了一个区间的包含关系。

于是借助这个结论，就可以很容易的完成整个子树的遍历，也可以很快速的获取整个子树里面所有的结点。

例如 { 3 , 5 , 6 } \{3,5,6\} {3,5,6} 这个结点的子树，很容易在里面找到 { 3 , 5 , 5 , 6 , 6 , 3 } \{3,5,5,6,6,3\} {3,5,5,6,6,3} 这个区间，恰好就对应的整个子树。这样会使很多的问题都处理地简单一些，尤其是关于子树的问题。

当我们遇到一些大力的 ds 题目的时候，例如需要快速修改子树里面的东西，可以不使用树链剖分，而是直接使用时间戳 + 线段树就行了。

另一个性质：如果把每一个点回溯时加入的数都删掉，剩余的数组成的就是 dfs 序。

这个东西很简单，由定义就可以很容易的证明。

void dfs(int u, int pre) {lpos[u] = ++dfn, id[dfn] = u;//刚刚遍历了这个结点，第一次加入for (auto i : v[u])if (i != pre)dfs(i, u);rpos[u] = dfn;//快要回溯了，第二次加入
}

代码很好理解。lpos 表示的是子树区间的左边界，rpos 表示的是子树区间的右边界。

CF877E Danil and a Part-time Job

我前面说过，这两个东西的定义和求解都是简单的，但是套到题目中就不一定简单了。所以我们现在开始讲题。

虽然这道题也是很简单的。

显然这个就是区间修改，有点像开关那道题目，直接先套上一个时间戳然后再线段树区间修改即可。

因为如果直接使用时间戳的话一个点会被计算两次，所以最后要 /2.

#include <bits/stdc++.h>
using namespace std;
const int N = 400010;
int val[N];
int c, a, b;
int n, m;int l[N], r[N], to[N], dfn;
vector<int> v[N];struct tree {int l, r, sum, add;
} t[N * 4];void build(int u, int x, int y) {t[u].l = x;t[u].r = y;if (x == y) {t[u].sum = val[to[x]];return ;}int mid = (x + y) >> 1;build(u * 2, x, mid);build(u * 2 + 1, mid + 1, y);t[u].sum = t[u * 2].sum + t[u * 2 + 1].sum;
}void tag(int u) {if (t[u].add == 0)return;t[u * 2].sum = t[u * 2].r - t[u * 2].l + 1 - t[u * 2].sum;t[u * 2 + 1].sum = t[u * 2 + 1].r - t[u * 2 + 1].l + 1 - t[u * 2 + 1].sum;if (t[u * 2].add == 0)t[u * 2].add = 1;elset[u * 2].add = 0;if (t[u * 2 + 1].add == 0)t[u * 2 + 1].add = 1;elset[u * 2 + 1].add = 0;t[u].add = 0;
}void change(int u, int l, int r) {if (l <= t[u].l && t[u].r <= r) {t[u].sum = t[u].r - t[u].l + 1 - t[u].sum;if (t[u].add == 0)t[u].add = 1;elset[u].add = 0;return ;}tag(u);int mid = (t[u].l + t[u].r) >> 1;if (a <= mid)change(u * 2, l, r);if (b > mid)change(u * 2 + 1, l, r);t[u].sum = t[u * 2].sum + t[u * 2 + 1].sum;
}int ask(int u, int l, int r) {if (l <= t[u].l && r >= t[u].r)return t[u].sum;tag(u);int mid = (t[u].l + t[u].r) / 2;int ans = 0;if (a <= mid)ans += ask(u * 2, l, r);if (b > mid)ans += ask(u * 2 + 1, l, r);return ans;
}void dfs(int u) {l[u] = ++dfn, to[dfn] = u;for (auto i : v[u])dfs(i);r[u] = ++dfn, to[dfn] = u;
}int main() {cin >> n;for (int i = 2; i <= n; i++) {int f;cin >> f;v[f].push_back(i);}for (int i = 1; i <= n; i++)cin >> val[i];dfs(1);build(1, 1, n * 2);cin >> m;for (int i = 1; i <= m; i++) {string c;int x;cin >> c >> x;a = l[x], b = r[x];if (c == "pow")change(1, l[x], r[x]);elsecout << ask(1, l[x], r[x]) / 2 << endl;}return 0;
}

代码长，思维简单。

CF1891F A Growing Tree

给定一棵树，一开始只含了 $1$ 个结点，编号为 $1$，初始权值为 $0$。设树的大小为 $sz$。

有 $q$ 次操作：

• $1x$，在 $x$ 下面挂一个结点，编号为 $sz+1$，初始的权值为 $0$。

• $2xv$，将当前 $x$ 子树中所有结点的权值加上 $v$。

---

乍一看好像无从下手：你这个加入会影响到很多结点的时间戳的值啊！于是正着在线处理操作是不行的。

这个时候有一个很重要的思想：正难则反。你正着加点不行，我反着来不行吗！

考虑离线处理操作。于是我们一开始就可以得出来把点全部加完之后的树。

如果遇到了 $2$ 操作，就像上一道题目一样使用区间修改维护即可。

如果遇到了 $1$ 操作，那么这个点先前的东西全部应该不算（到了这个时候这个点才加进来！它的整个子树也是一样！），所以要把整个子树都减去自己现在的权值。

所以就只需要一个支持区间加单点查询的数据结构即可，很容易想到使用树状数组加上差分，因为线段树 lazytag 还是太难写了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t;
int n;
const int N = 1000010;struct node {int op, x, v;
} a[N];
vector<int> v[N];
int ans[N], x[N];
int l[N], r[N], dfn;void dfs(int u) {l[u] = ++dfn;for (auto i : v[u])dfs(i);r[u] = ++dfn;
}struct BIT {int tree[N];void clear() {for (int i = 1; i <= n * 2; i++)tree[i] = 0;}void add(int pos, int val) {for (; pos <= n * 2; pos += pos & -pos)tree[pos] += val;}int query(int pos) {int ans = 0;for (; pos; pos -= pos & -pos)ans += tree[pos];return ans;}
} st;signed main() {cin >> t;while (t--) {cin >> n;dfn = 0;int sz = 1;for (int i = 1; i <= n; i++) {cin >> a[i].op;if (a[i].op == 2)cin >> a[i].x >> a[i].v;elsecin >> a[i].x, v[a[i].x].push_back(++sz), x[i] = sz;}dfs(1);st.clear();for (int i = 1; i <= n; i++) {if (a[i].op == 2) {st.add(l[a[i].x], a[i].v);st.add(r[a[i].x] + 1, -a[i].v);} else if (!ans[x[i]]) {int a = st.query(l[x[i]]);st.add(l[x[i]], -a), st.add(r[x[i]] + 1, a);}}for (int i = 1; i <= sz; i++)cout << st.query(l[i]) << " ";cout << endl;for (int i = 1; i <= sz; i++)v[i].clear(), l[i] = r[i] = 0, ans[i] = 0, x[i] = 0;}return 0;
}

AT_abc294_g [ABC294G] Distance Queries on a Tree

给定一棵 $n$ 点的树，带边权，进行 $Q$ 次操作，共有两种：

• 1 i w 将第 $i$ 条边的边权改为 $w$。

• 2 u v 询问 $u,v$ 两点的距离。

---

设 $1$ 为树根。

很显然，第二个询问可以使用 LCA 来求解（因为树的形态始终不变，LCA 也不会变）。设 $d_i$ 表示 $1\to i$ 的边权和，那么 $u,v$ 的距离为 $d_u+d_v-2\times d_{lca(u,v)}$。所以第二个询问可以 $O(\log n)$ 快速求解。

考虑如何处理第一个询问。很显然，设 $i$ 为 $u\to v$ 的边（不妨让 $u$ 的深度比 $v$ 浅），则当 $u\to v$ 的边权改变的时候（设相比原来多了 $w$），有且仅有 $v$ 子树里面的 $d$ 值会发生改变，具体地，改变幅度就是 $w$。

所以就是子树修改，可以直接序列化。

好久之前做的了，可能和现在的码风略有不同。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_N = 2e5 + 5, LOG_MAX_N = 19;int n;
struct Edge {int u, v, w;
};
Edge edge[MAX_N];
vector<int> adj[MAX_N];
int q;int n_ind, start_ind[MAX_N], end_ind[MAX_N];
int anc[MAX_N][LOG_MAX_N];
void dfs(int u) {start_ind[u] = ++n_ind;for (auto& v : adj[u]) {if (start_ind[v]) anc[u][0] = v;else dfs(v);}end_ind[u] = n_ind;
}bool is_anc(int u, int v) {return start_ind[u] <= start_ind[v] && start_ind[v] <= end_ind[u];
}
int lca(int u, int v) {if (is_anc(u, v)) return u;if (is_anc(v, u)) return v;for (int i = ceil(log2(n)); i >= 0; i--) {if (anc[u][i] == 0 || is_anc(anc[u][i], v)) continue;u = anc[u][i];}return anc[u][0]; }int segtree[4 * MAX_N];
void update(int l, int r, int x, int u = 1, int lo = 1, int hi = n) {if (l <= lo && hi <= r) {segtree[u] += x;return;}int mid = (lo + hi) / 2;if (l <= mid) update(l, r, x, 2 * u, lo, mid);if (r > mid) update(l, r, x, 2 * u + 1, mid + 1, hi);
}
int query(int i, int u = 1, int lo = 1, int hi = n) {if (lo == hi)return segtree[u];int mid = (lo + hi) / 2;if (i <= mid) return segtree[u] + query(i, 2 * u, lo, mid);else return segtree[u] + query(i, 2 * u + 1, mid + 1, hi);
}signed main() {// freopen("dist.in", "r", stdin);// freopen("dist.out", "w", stdout);cin >> n;for (int i = 1; i < n; i++) {int u, v, w; cin >> u >> v >> w;edge[i] = {u, v, w};adj[u].push_back(v);adj[v].push_back(u);}cin >> q;dfs(1);for (int i = 1; i <= ceil(log2(n)); i++) {for (int j = 1; j <= n; j++) {anc[j][i] = anc[anc[j][i - 1]][i - 1];}}for (int i = 1; i < n; i++) {int u = edge[i].u, v = edge[i].v;if (start_ind[u] > start_ind[v]) swap(u, v);update(start_ind[v], end_ind[v], edge[i].w); }    for (int xq = 1; xq <= q; xq++) {int t, a, b; cin >> t >> a >> b;if (t == 1) {int u = edge[a].u, v = edge[a].v;if (start_ind[u] > start_ind[v]) swap(u, v);update(start_ind[v], end_ind[v], b - edge[a].w);edge[a].w = b;} else {int ans = query(start_ind[a]) + query(start_ind[b]) - 2 * query(start_ind[lca(a, b)]);cout << ans << '\n';}}
}

CF1328E Tree Queries

接下来开始讲蓝紫题，坐稳了！

前情提要：

我很好奇为什么 CF 要搞这么多测试点。

---

进入正题。给你一个 $1$ 为根的有根树，每次询问 $k$ 个结点 $v_1,v_2,\cdots ,v_k$，求是否有一条以根结点为一端的链使得询问的每一个结点到这条链的距离都是 $\le 1$。

这道题看似很不友善，实际上全部的过程就只有两句话。

个人感觉这道题还是很妙的，可能是我太菜了吧。

---

首先，考虑如何判断多个点在同一条一端为根的链上。

这个任务非常的简单，好像有一万种方法，这也使得选择较为困难。

考虑挖掘性质。首先，这一条链上面的每一个深度都最多出现一次，这是显然的。所以对深度排序。

排序完了之后咋办呢？显然，这样的一条链上的相邻两个点都是由祖先的关系。所以如果这堆点在同一条链上面的话，排序之后相邻的点一定存在祖孙关系。

这个时候又有了一万种方法，但是我们要选择最快的。既然都出现祖孙关系了，那么还不够启发吗？显然，祖先的子树里面一定包含子孙，所以直接使用时间戳判断区间包含即可。

也可以使用 lca 来判断。

---

但是，上面的东西和题目只有一点关联。因为题目要我们求的是距离 $\le 1$。

**继续挖掘性质！**这个链的一端是根结点，所以可以得出两个结论：

• 如果一个结点在这条链上，则其父亲也一定在链上，也就是距离 $=0$ 一定在链上。（废话）

• 如果一个结点的父亲不在链上，则它也一定不会在链上，则就是距离 $>1$ 的时候一定不在链上。

也就是，一个点距离这条链的距离是否 $\le 1$，和它的父亲是不是在链上有关。

所以每一个点变成它的父亲，然后再判断是不是在一条链上面即可。

注意，这里设根结点的父亲是它自己，要不然就出问题了。

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 200010;
int fa[N];
vector<int> v[N];
bool fg[N];
int f[N][30];
int cnt;
int a[N], dep[N];
bool ok;void dfs(int u, int pre) {f[u][0] = pre;dep[u] = dep[pre] + 1;for (int i = 1; i <= 20; ++i)f[u][i] = f[f[u][i - 1]][i - 1];for (auto i : v[u])if (i != pre)dfs(i, u);
}int lca(int x, int y) {if (dep[x] > dep[y])swap(x, y);for (int i = 20; i >= 0; --i)if (dep[f[y][i]] >= dep[x])y = f[y][i];if (y == x)return x;for (int i = 20; i >= 0; --i)if (f[y][i] != f[x][i])y = f[y][i], x = f[x][i];return f[x][0];
}void get_fa(int u, int pre) {fa[u] = pre;for (auto i : v[u])if (i != pre)get_fa(i, u);
}bool cmp(int x, int y) {return dep[x] < dep[y];
}int main() {cin >> n >> m;for (int i = 1; i < n; i++) {int x, y;cin >> x >> y;v[x].push_back(y);v[y].push_back(x);}get_fa(1, 0);dfs(1, 0);while (m--) {int k;cin >> k;int tot = 0;for (int i = 1; i <= k; i++) {int x;cin >> x;if (x != 1)a[++tot] = fa[x], fg[fa[x]] = 1;}sort(a + 1, a + tot + 1, cmp);cnt = unique(a + 1, a + tot + 1) - a - 1;ok = 1;for (int i = 1; i < cnt; i++)if (lca(a[i], a[i + 1]) != a[i])ok = 0;for (int i = 1; i <= cnt; i++)fg[a[i]] = 0;if (ok)cout << "YES\n";elsecout << "NO\n";}return 0;
}

CF383C Propagating tree

有一棵树，上面有 $n$ 个结点。它的根是 $1$ 号节点。

这棵橡树每个点都有一个权值，你需要完成这两种操作：

$1$ $u$ $val$ 表示给 $u$ 节点的权值增加 $val$。

$2$ $u$ 表示查询 $u$ 节点的权值。

它还有个神奇的性质：当某个节点的权值增加 $val$ 时，它的子节点权值都增加 $-val$，它子节点的子节点权值增加 $-(-val)$… 如此一直进行到树的底部。

---

很显然直接把树的深度分成奇偶性，每一个开一个线段树再记录一下 dfs 序，然后分类讨论即可。

有一些细节。

// LUOGU_RID: 168542341
#include <bits/stdc++.h>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)
using namespace std;
const int N = 200010;
int n, m;
int val[N];
int dd[N * 2][2]; //两个dfs序，一个是奇数层，一个是偶数层的
int tot;
vector<int> v[N];
int dep[N];//深度void dfs(int u, int pre) { //求dfs序dep[u] = dep[pre] + 1;tot++;dd[tot][dep[u] % 2] = u;for (auto i : v[u])if (i != pre)dfs(i, u);tot++;dd[tot][dep[u] % 2] = u;
}struct segment_tree {int seg[N * 4 * 2], lazy[N * 4 * 2];void pushup(int now) {seg[now] = seg[ls(now)] + seg[rs(now)];}void pushdown(int now, int l, int r) {if (lazy[now] != 0) {lazy[ls(now)] += lazy[now];lazy[rs(now)] += lazy[now];seg[ls(now)] += (mid - l + 1) * lazy[now];seg[rs(now)] += (r - mid) * lazy[now];lazy[now] = 0;}}void build(int now, int l, int r, int wh) {lazy[now] = 0;if (l == r) {seg[now] = val[dd[l][wh]];return ;}build(ls(now), l, mid, wh);build(rs(now), mid + 1, r, wh);pushup(now);}void update(int now, int l, int r, int ql, int qr, int val) {if (l >= ql && r <= qr) {lazy[now] += val;seg[now] += (r - l + 1) * val;return ;}pushdown(now, l, r);if (ql <= mid)update(ls(now), l, mid, ql, qr, val);if (qr > mid)update(rs(now), mid + 1, r, ql, qr, val);pushup(now);}int query(int now, int l, int r, int pos) {if (l == r)return seg[now];pushdown(now, l, r);if (pos <= mid)return query(ls(now), l, mid, pos);elsereturn query(rs(now), mid + 1, r, pos);}
} sg1, sg2;
int pot[N][2];int main() {ios::sync_with_stdio(0);cin >> n >> m;for (int i = 1; i <= n; i++)cin >> val[i];for (int i = 1; i < n; i++) {int x, y;cin >> x >> y;v[x].push_back(y);v[y].push_back(x);}dfs(1, 0);sg1.build(1, 1, 2 * n, 0);sg2.build(1, 1, 2 * n, 1);for (int i = 1; i <= 2 * n; i++) {if (pot[dd[i][0]][0] == 0)pot[dd[i][0]][0] = i;elsepot[dd[i][0]][1] = i;if (pot[dd[i][1]][0] == 0)pot[dd[i][1]][0] = i;elsepot[dd[i][1]][1] = i;}while (m--) {int op;cin >> op;if (op == 1) {int x, y;cin >> x >> y;sg1.update(1, 1, 2 * n, pot[x][0], pot[x][1], (dep[x] % 2 == 1 ? -y : y));sg2.update(1, 1, 2 * n, pot[x][0], pot[x][1], (dep[x] % 2 == 0 ? -y : y));} else {int x;cin >> x;if (dep[x] % 2 == 0)cout << sg1.query(1, 1, 2 * n, pot[x][0]) << endl;elsecout << sg2.query(1, 1, 2 * n, pot[x][0]) << endl;}}return 0;
}