等级森严
time limit per test 2 second memory limit per test 256 megabytes
武林,当然有拉帮结派,帮派之间还有吞并现象。那么两个人见面,常常要问,咱俩是自己人吗?如果是自己人,他们还想知道他们两个人的等级差多少。你需要做的就是快速回答这个问题。
武林中共有 N 个人,编号分别为 1~N,有 M 条命令,两种格式:
1 x y:编号为 x 和 y 的两个人所在的帮派合并了,x 的帮派的帮主归于 y 的门下,y 的等级比 x 的帮派的帮主高一级(如果 x 和 y 已经在一个帮派中,则跳过这条命令。);
2 x y:请回答编号为 x 和 y 的两个人是否是自己人。

开始的时候,没有两个人属于同一个帮派,每个人都是自己帮派的帮主。

传送门:SHUOJ1880

Input

第一行包含两个整数 N, M,接下来 M 行,每行 3 个整数 t x y,表示一条命令。 0 < N, M < 1e5 0 < t < 3 0 < x, y < N + 1 且 x 不等于 y

Output

对于每条第二种命令,输出 "Yes" 或 "No",如果 Yes,还需要输出两者的等级差。

Sample Input

1
2
3
4
5
6
7
3 6
2 1 2
1 1 2
2 1 2
2 2 3
1 2 3
2 3 1

Sample Output

1
2
3
4
No
Yes -1
No
Yes 2

题解

路径压缩时的 记录点到根距离的带权并查集 注意点到父亲距离不一定是加一,因为路径压缩过了,所以最好+=父亲距离
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.io.*;  
import java.util.*;
public class Main {
static int[]pre;
static int[]sum;
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
while(sc.hasNext()){
int n=sc.nextInt();
int m=sc.nextInt();
pre=new int[n+1];
sum=new int[n+1];
for(int i=1;i<=n;i++){
pre[i]=i;
sum[i]=0;
}
for(int k=1;k<=m;k++){
int a=sc.nextInt();
int x=sc.nextInt();
int y=sc.nextInt();
if(a==1){
if(find(x)!=find(y)){
pre[find(x)]=y;
}
}else{
if(find(x)!=find(y)){
pw.println("No");
}else{
pw.print("Yes ");
pw.println(sum[y]-sum[x]);
}
}
}
pw.flush();
}
}
static int find(int x) {
if(x == pre[x]) return x;
else {
int root = find(pre[x]);
if(sum[x]==0)
sum[x] = sum[pre[x]]+1;
else
sum[x] += sum[pre[x]];
return pre[x] = root;
}
}
}