带权并查集:
1 #include<stdio.h>
2 #include<string.h>
3 using namespace std;
4 int f[1000010];
5 int sum[1000010];
6 int find(int x)
7 {
8 if(x!=f[x])
9 {
10 int pre=f[x];//pre是x的一个父节点。
11 f[x]=find(f[x]);//递归找祖先。
12 sum[x]+=sum[pre];
13 }
14 return f[x];
15 }
16 int main()
17 {
18 int n;
19 while(~scanf("%d",&n))
20 {
21 for(int i=0;i<=n;i++)
22 {
23 f[i]=i;
24 sum[i]=0;
25 }
26 int op;
27 while(n--)
28 {
29 scanf("%d",&op);
30 if(op==1)
31 {
32 int x,y,val;
33 scanf("%d%d%d",&x,&y,&val);
34 int X=find(x);
35 int Y=find(y);
36 if(X!=Y)
37 {
38 sum[Y]=val-sum[y]+sum[x];
39 f[Y]=X;
40 }
41 }
42 else
43 {
44 int x,y;
45 scanf("%d%d",&x,&y);
46 int X=find(x);
47 int Y=find(y);
48 if(X!=Y)
49 {
50 printf("?\n");
51 }
52 else
53 {
54 printf("%d\n",sum[y]-sum[x]);
55 }
56 }
57 }
58 }
59 }