Les arêtes sont ajoutées à un graphe pondéré non orienté. Écrivez un programme qui, à un moment donné, trouve la somme des poids des arêtes dans un composant connexe.
La première ligne contient deux nombres
n
et
m
(1 <= n, m <= 10
6) - le nombre de sommets dans la colonne et le nombre d'ajouts et de requêtes effectués. Elle est suivie de lignes
m
décrivant l'ajout ou la demande. Chaque ligne est composée de deux ou quatre chiffres. Le premier des chiffres indique le code de fonctionnement. Si le premier nombre est
1
, il est suivi de trois autres nombres
x
,
y
,
w
. Cela signifie qu'une arête est ajoutée au graphe du sommet
x
au sommet
y
de poids
w
. (1 <= x < y <= n, 1 <= w <= 10
3). Plusieurs arêtes sont autorisées. Si le premier nombre est
2
, alors exactement un nombre
x
le suit. Cela signifie qu'il est nécessaire de répondre à la question, quelle est la somme des arêtes de la composante connexe à laquelle appartient le sommet
x
(1 <= x <= n). div>
Sortie
Pour chaque opération avec le code
2
imprimer la réponse au problème donné. Imprimez la réponse à chaque demande sur une ligne distincte.
Exemples
# |
Entrée |
Sortie |
1 |
6 10
2 1
1 1 2 1
2 1
1 2 4 2
2 1
1 1 4 3
2 1
1 3 5 3
2 5
2 6
0
1
3
6
3
0