先膜毛爷爷。
题目描述
给出一棵动态的树，有一个集合 \(S\)，每次询问集合中的所有点相连的路径是否一定经过 \((x, y)\)。
四种操作： - \(\text{opt} = 1, x, y, u, v\)：删除边 \((x, y)\)，增加边 \((u, v)\)； - \(\text{opt} = 2, x, y\)：在集合 \(S\) 中加入 \((x, y)\)； - \(\text{opt} = 3, x\)：删除第 \(x\) 个加入集合 \(S\) 的点对； - \(\text{opt} = 4, x, y\)：询问集合中的所有点相连的路径是否一定经过 \((x, y)\)。
| 测试点编号 | \(n\) | \(m\) | \(\text{type}\) | 限制 |
|---|---|---|---|---|
| 1 | \(n \le 100\) | \(m \le 100\) | 1, 2, 3, 4 | |
| 2, 3 | \(n \le 100000\) | \(m \le 300000\) | 2, 4 | |
| 4, 5 | 2, 3, 4 | |||
| 6, 7 | 1, 2, 3, 4 | \(\mid S\mid \le 10\) | ||
| 8, 9, 10 | 1, 2, 3, 4 |
题解
对于测试点 1，可以暴力。可以用一个 set 维护边的信息，对于加边删边直接用 set 的 insert 和 erase，每次暴力遍历 s 中的所有点对走一遍看是否经过边 \((x, y)\)。
对于测试点 2、3、4、5，因为没有加边删边操作，所以每次将加入点对 \((x, y)\) 这条链上的值 \(+1\)，每次查询时判断 \((x, y)\) 上的和是否为 \(\mid S \mid\)，正确性显然。因为不改变树的形态，而且维护的是一条链的信息，所以树链剖分和 LCT 应该都可以。
对于测试点 6、7，可以用 LCT，因为 \(\mid S \mid \le 10\)，所以在删边的时候可以暴力枚举 \(10\) 种的变化。
暂时只会 \(70\) 分吧。
哦我好像想到正解了 (Update 2020.7.17 20点左右)。
考虑当 \(u\) 为根的时候，如果所有路径都经过 \((u, v)\)，那么对于 \(S\) 中的所有点对 \((x, y)\)，其路径有且仅有一个端点在以 \(x\) 为根 \(y\) 的子树中。
那么如何判断？
假设现在有一种数据类型 \(\text{Type}\)，它支持一个操作 \(\text{operator}\) 满足 \(x \ \ \text{operator} \ \ x = 0\) 和 \(0 \ \ \text{operator} \ \ x = x\)，且有一个 \(\text{Type} \ \ ans\)，那么在加进边的时候，把 \(ans \ \ \text{operator}\ \ rnd()\)，删边时 \(\text{operator}\) 回去。那么可以记录整棵树的 \(ans\)，每次询问以 \(x\) 为根 \(y\) 的子树的值，如果满足所有点对 \((u, v)\) 都经过 \((x, y)\) 这条边，那么该值应该等于 \(ans\)。
我选择用了异或，如果加减法混合用应该也可以。
维护子树信息，Top Tree。
LCT 维护的是实链的信息，对于除了 Access 和 Link 的操作并不会改变虚边的信息。
如果只考虑实链，那么 PushUp 是这样写： 1
void PushUp(int x) { sze[x] = sze[ch[x][0]] ^ sze[ch[x][1]] ^ v[x]; }
然后考虑虚链。
用 \(sze_x\) 表示 \(x\) 的子树虚链信息，\(v_x\) 表示 \(x\) 的信息。
Access(x) 操作：断 \(ch_{x, 1}\)，连 \(i\)。
1
2
3
4
5
6
7void Access(int x) {
for (int i = 0; x; i = x, x = fa[x]) {
Splay(x);
v[x] ^= sze[ch[x][1]], v[x] ^= sze[ch[x][1] = i];
PushUp(x);
}
}Link(x, y) 操作：连 \(y\)。
1
void Link(int x, int y) { Split(x, y), fa[x] = y, v[y] ^= sze[x], PushUp(y); }
挺显然的
1 |
|