306243: CF1166F. Vicky's Delivery Service
Memory Limit：256 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Vicky's Delivery Service
题意翻译
有n个点，m条边的图，每条边有一种颜色。定义一条路（经过的点是$c1,c2,.......cn$）是彩虹路，要求满足2个条件： 1.对于所有$1<=i<n$ $c_i$和$c_{i+1}$有边 2.对于所有$1<=i<\frac{n-1}{2}$，$c_{2i}$和$c_{2i-1}$的边的颜色与$c_{2i}$和$c_{2i+1}$的边的颜色相同 现在有$q$个操作： 1.加入一条颜色为$w$，连接$u,v$的边 2.询问两个点$u,v$之间是否有一条彩虹路题目描述
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.输入输出格式
输入格式
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.
输出格式
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.
输入输出样例
输入样例 #1
4 3 2 4
1 2 1
2 3 1
3 4 2
? 1 4
? 4 1
+ 3 1 2
? 4 1
输出样例 #1
Yes
No
Yes