Weighted and lookup set:
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 is a parent of x. 11 f[x]=find(f[x]); // find the ancestor recursively. 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}Copy the code