7.24 树上问题2笔记

题单

T1

题目
• 有一棵点数为 \(n\) 的树。
• 有 \(q\) 次询问，每次询问有多少个点到 \(a, b\) 距离相等。
• \(1 ≤ n\), \(q ≤ 500000\)。

Solution

• 设询问 \(a, b\) 两点直接的路长度为 \(d\)。
• 如果 \(d\) 为奇数，那么无解，\(d\) 为偶数有解。
• 考虑以下几种情况：

1. \(a, b\) 到 \(LCA(a, b)\) 的距离相等，那么 \(LCA(a, b)\) 中除了包含 \(a, b\) 的两棵子树上的点，其他点都满足。
2. \(a, b\) 到 \(LCA(a, b)\) 的距离不相等，假设 \(a\) 到 \(LCA(a, b)\) 距离更远，则中点到 \(a, b\) 的距离为 \(\frac {d}{2}\)。从 \(a\) 为起点往上走 \(\frac {d}{2}\) 的距离，设该点为 \(c\)，那么 \(c\) 为根的子树，除了 \(a\) 所在的子树，其他点都可以作为中点。

• 时间复杂度为 \(\mathcal {O}(q log n)\)。

T2

题目

• 给你一个以 \(1\) 为根的有根树。
• 每回询问 \(k\) 个节点，\(v_2, v_2, \cdots v_k\)。
• 求出是否有一条以根节点为一端的链使得询问的每个节点到此链的距离均 \(≤ 1\)。
• 只需输出可行性, 无需输出方案。
• \(n, k, \sum k ≤ 200000\)。

Solution

• 如果要经过一个节点，会有三种情况：

1. 经过它的父亲。
2. 经过它本身。
3. 经过它的两个及以上的儿子（这样才能覆盖节点）。

• 但是题目给的是一个有根树，所以要想经过一个节点或者它的儿子就必须经过它的父亲，所以题目就变成了让我们满足链经过给出节点的父亲节点。
• 我们可以按照深度从小到大排序后，依次判断相邻两个点中深度大的是否在深度小的子树内即可，可以用 \(dfn\) \(\mathcal{O}(1)\) 判断。

T3

题目

blog

T4

题目
• 给一棵 \(n\) 个节点的树，每个点为黑色或白色，一次操作可以使一个相同颜色的连通块变成另一种颜色，求使整棵树变成一种颜色的最少操作数。
• \(n ≤ 200000\)。

Solution

• 神仙题。。。
• 遍历所有的边，如果边的两端颜色不一样，那么就将这条边权置成 \(1\)，最后求树的直径即可。就这么简单。。。

T5

题目
• 有一棵点数为 \(n\) 的树，以点 \(1\) 为根。
• 有 \(m\) 个操作，分为两种：

1. \(1\) \(x\) \(a\)：将 \(x\) 为根的子树涂上 \(a\) 号颜色 (颜色不会覆盖，全部共存)
2. \(2\) \(x\)：询问 \(x\) 为根的子树颜色丰富度，表示为所有子树节点颜色种类数相加 (每个点单独计算)
   • \(n, m ≤ 100000\)。

Solution

• 码量巨大的sb题。
• 可以利用时间戳的性质（同个子树内节点编号是连起来的）写线段树。
• 然后维护一个 \(set\)，存储每种颜色哪些点染上了。但是点太多了，直接存储肯定是不行的，然后就可以发现：

1. 如果点 \(x\) 要染上颜色 \(x\)，那么他在 \(set\) 里的子孙就可以删除了，这点可以暴力实现。
2. 然后如果点 \(x\) 要染上 \(c\)，且发现他的祖先已经在 \(set\) 中，就是染过了，那么这次修改就可以忽略了。

T6

题目
• 给定 \(n\) 个节点的树，\(1\) 为根节点，每个节点是一个 ‘(’ 或者 ‘)’。
• \(1\) 到每一个节点 \(x\) 的路径是一个括号序列，记括号序列中子串是合法括号序列的数量为 \(k_x\)。
• 计算出 \((1 \cdot k_1)⊕(2 \cdot k_2)⊕· · ·⊕(n \cdot k_n)\)。
• \(n ≤ 500000\)。

Solution

贺的题解
• 首先表示状态。
• \(f_i\) 表示 \(i\) 这个节点到根节点的合法括号序列数。
• \(last_i\) 表示 \(i\) 到根上一个没有匹配的 ')' 的位置。
• \(line_i\) 表示 \(i\) 到根的路径上连续已经匹配的括号串数。
• 考虑转移。
• 如果这个节点是 '('，那么 \(f_i\) 以及 \(line_i\) 都是直接继承父节点的，所以 \(last_i\) 就是 \(i\)。
• 如果是 ')'，但 \(last_i\) 不存在，这个括号就无效了。
• 如果是 ')'，且 \(last_i\) 存在，那么就有以下转移：

1. \(last[u] = last[fa[last[u]]]\)，也就是说 \(u\) 和 \(last[u]\) 匹配之后上一个没有匹配的就是 \(last[fa[last[u]]]\)。
2. \(line[u]=line[fa[last[u]]]+1\)，也就是说连续的括号数是 \(fa[last[u]]\) 的连续括号数加 \(1\)。
3. \(f[u]=f[fa[u]]+line[u]\)，这里匹配了之后，会形成 \(line[u]\) 个新的合法串。

• 遍历一遍即可。