CF1166F Vicky's Delivery Service

在一个魔法世界里，有 $n$ 个城市，编号为 $1, 2, \dots, n$。其中一些城市之间通过有颜色的魔法道路相连。由于魔法不稳定，任何时刻都有可能出现新的道路连接两个城市。 女巫 Vicky 被要求在一些城市对之间进行配送。然而，Vicky 还是个新手，她只能在能够通过“双彩虹”从起点城市到达终点城市时完成配送。一个“双彩虹”是指满足以下条件的城市序列 $c_1, c_2, \dots, c_k$： - 对于每个 $i$，$1 \le i \le k - 1$，城市 $c_i$ 和 $c_{i+1}$ 之间有一条道路相连。 - 对于每个 $i$，$1 \le i \le \frac{k-1}{2}$，连接 $c_{2i}$ 与 $c_{2i-1}$ 的道路和连接 $c_{2i}$ 与 $c_{2i+1}$ 的道路颜色相同。 例如，如果 $k = 5$，那么 $c_1$ 和 $c_2$ 之间的道路颜色必须与 $c_2$ 和 $c_3$ 之间的道路颜色相同，$c_3$ 和 $c_4$ 之间的道路颜色必须与 $c_4$ 和 $c_5$ 之间的道路颜色相同。 Vicky 有一个按时间顺序排列的事件列表，每个事件要么是她需要完成的一次配送，要么是有一条新道路出现。请帮助她判断每次配送是否能够完成。

第一行包含四个整数 $n$、$m$、$c$ 和 $q$（$2 \le n \le 10^5$，$1 \le m, c, q \le 10^5$），分别表示城市数量、初始道路数量、道路可能的颜色数以及事件数量。 接下来的 $m$ 行，每行包含三个整数 $x$、$y$ 和 $z$（$1 \le x, y \le n$，$1 \le z \le c$），表示城市 $x$ 和 $y$ 之间初始存在一条颜色为 $z$ 的双向道路。 接下来有 $q$ 行，每行描述一个事件，事件有两种类型： 1. + x y z（$1 \le x, y \le n$，$1 \le z \le c$），表示城市 $x$ 和 $y$ 之间出现一条颜色为 $z$ 的道路； 2. ? x y（$1 \le x, y \le n$），表示你需要判断 Vicky 是否可以从城市 $x$ 出发，通过“双彩虹”到达城市 $y$。保证 $x \neq y$。 保证任意时刻，任意一对城市之间最多只有一条道路相连，且没有城市与自身相连。保证输入中至少有一个第二类事件。

对于每个第二类事件，输出一行，如果可以完成配送则输出 "Yes"（不含引号），否则输出 "No"（不含引号）。

下图对应样例输入。  对于第一次配送，Vicky 可以使用序列 $1, 2, 3, 4$，这是一个“双彩虹”。但她无法完成第二次配送，因为她只能到达城市 $3$。在添加了城市 $1$ 和 $3$ 之间的道路后，她可以通过序列 $4, 3, 1$ 完成从城市 $4$ 到城市 $1$ 的配送。 由 ChatGPT 4.1 翻译