Vicky's Delivery Service
Contest: Codeforces Round 561 (Div. 2)
Difficulty rating: 2400
Tags: data structures, dsu, graphs, hashing

In a magical land there are $$$n$$$ cities conveniently numbered $$$1, 2, \dots, n$$$. Some pairs of these cities are connected by magical colored roads. Magic is unstable, so at any time, new roads may appear between two cities.

Vicky the witch has been tasked with performing deliveries between some pairs of cities. However, Vicky is a beginner, so she can only complete a delivery if she can move from her starting city to her destination city through a double rainbow. A double rainbow is a sequence of cities $$$c_1, c_2, \dots, c_k$$$ satisfying the following properties:

- For each $$$i$$$ with $$$1 \le i \le k - 1$$$, the cities $$$c_i$$$ and $$$c_{i + 1}$$$ are connected by a road.
- For each $$$i$$$ with $$$1 \le i \le \frac{k - 1}{2}$$$, the roads connecting $$$c_{2i}$$$ with $$$c_{2i - 1}$$$ and $$$c_{2i + 1}$$$ have the same color.

For example if $$$k = 5$$$, the road between $$$c_1$$$ and $$$c_2$$$ must be the same color as the road between $$$c_2$$$ and $$$c_3$$$, and the road between $$$c_3$$$ and $$$c_4$$$ must be the same color as the road between $$$c_4$$$ and $$$c_5$$$.

Vicky has a list of events in chronological order, where each event is either a delivery she must perform, or appearance of a new road. Help her determine which of her deliveries she will be able to complete.

Input format:
The first line contains four integers $$$n$$$, $$$m$$$, $$$c$$$, and $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le m, c, q \le 10^5$$$), denoting respectively the number of cities, the number of roads initially present, the number of different colors the roads can take, and the number of events.

Each of the following $$$m$$$ lines contains three integers $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1 \le x, y \le n$$$, $$$1 \le z \le c$$$), describing that there initially exists a bidirectional road with color $$$z$$$ between cities $$$x$$$ and $$$y$$$.

Then $$$q$$$ lines follow, describing the events. Each event is one of the following two types:

1. + x y z ($$$1 \le x, y \le n$$$, $$$1 \le z \le c$$$), meaning a road with color $$$z$$$ appears between cities $$$x$$$ and $$$y$$$;
2. ? x y ($$$1 \le x, y \le n$$$), meaning you should determine whether Vicky can make a delivery starting at city $$$x$$$ and ending at city $$$y$$$. It is guaranteed that $$$x \neq y$$$.

It is guaranteed that at any moment, there is at most one road connecting any pair of cities, and that no road connects a city to itself. It is guaranteed that the input contains at least one event of the second type.

Output format:
For each event of the second type, print a single line containing "Yes" (without quotes) if the delivery can be made, or a single line containing "No" (without quotes) otherwise.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
The following picture corresponds to the sample.

For her first delivery, Vicky can use the sequence 1, 2, 3, 4 which is a double rainbow. However, she cannot complete the second delivery, as she can only reach city $$$3$$$. After adding the road between cities $$$1$$$ and $$$3$$$, she can now complete a delivery from city $$$4$$$ to city $$$1$$$ by using the double rainbow 4, 3, 1.

Example input:
4 3 2 4
1 2 1
2 3 1
3 4 2
? 1 4
? 4 1
+ 3 1 2
? 4 1

Example output:
Yes
No
Yes

Editorial:
Let $$$G$$$ be the graph with cities as vertices and roads as edges. Note that the edges originally in $$$G$$$ can be regarded as $$$m$$$ queries of the "add edge" type, so we will just describe a solution that can handle $$$m + q$$$ queries of any type.
We need a way to capture the idea of going through two roads of the same color in a row. To do this, consider a graph $$$G^*$$$ with the same vertices as $$$G$$$, in which vertices $$$u$$$ and $$$v$$$ are connected by an edge if $$$uw$$$ and $$$vw$$$ are edges of the same color for some vertex $$$w$$$. Then any path in this graph corresponds to a double rainbow in the original. However, this doesn't solve the problem yet, because of the condition that the final edge of a double rainbow can be of any color.
To help in solving this issue, consider $$$n$$$ sets $$$S_v$$$ such that $$$S_v$$$ has all of the $$$G^*$$$-connected components of both $$$v$$$ and any neighbor of $$$v$$$. Then we can see that we have a double rainbow from $$$u$$$ to $$$v$$$ if and only if the connected component of $$$u$$$ is in $$$S_v$$$ (either we reach $$$v$$$ directly, or we reach one of its neighbors and then use our final edge to go to $$$v$$$). So as long as we can mantain these sets, we have a $$$\mathcal{O}(\log n)$$$ time way to answer queries of the second type.
Now we need to deal with adding edges. To do this, we will store the connectivity of $$$G^*$$$ using a DSU. When we connect two connected components in $$$G^*$$$, we do the merges from small to large. If we merge component $$$b$$$ into component $$$a$$$ then for each vertex $$$u$$$ in component $$$b$$$ and every neighbor $$$v$$$ of $$$u$$$ we remove $$$b$$$ from $$$S_v$$$ and insert $$$a$$$ instead. By merging from small to large we guarantee that each vertex changes component at most $$$\mathcal{O}(\log n)$$$ times, and thus we also update $$$S_v$$$ through the edge $$$uv$$$ at most $$$\mathcal{O}(\log n)$$$ times. Each update is just two $$$\mathcal{O}(\log n)$$$ operations, so over all updates this amortizes to $$$\mathcal{O}((m + q)\log(n)^2)$$$ (because we have $$$\mathcal{O}(m + q)$$$ edges), plus $$$\mathcal{O}(n \log n)$$$ for actually moving the vertices.
There's an easy to fix, but important note, which is that the number of edges in $$$G^*$$$ can be quadratically large. However, we can check that for each edge $$$uv$$$ of color $$$x$$$ that we add, we only need to add two edges to $$$G^*$$$. Namely, if $$$u'$$$ and $$$v'$$$ are neighbors of $$$u$$$ and $$$v$$$ respectively through an edge of color $$$x$$$, then it is enough to add edges $$$uv'$$$ and $$$u'v$$$. (If one of $$$u'$$$ or $$$v'$$$ doesn't exist then we just don't add the corresponding edge). We can store these $$$x$$$-colored neighbors of each vertex in sets which have total size at most $$$m + q$$$, so we can find in $$$\mathcal{O}(\log n)$$$ which updates we need to perform, and we perform a constant number of updates per added edge.
Complexity: $$$\mathcal{O}(n \log(n) + (m + q)\log(n)^2)$$$, or $$$\mathcal{O}((n + m + q)\log(n))$$$ using hash tables.