# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Name |
---|
It is not necessary that the
a[i]
will hold the actual value of the root for every node. You need to useroot(i)
to get the root node. See your solution AC Here.The only difference is finding the actual root for a node
i
.Why does A[i] not hold the actual value of the root?
Initially,
a[i]
(From now onparent
) just points to itself.During merging, The parent of the root of the set with the smaller size ( count of nodes in it) is changed to the root of the set with the larger size. ( We don't change the parent of all the nodes in the smaller sized state hence they do not always hold the correct value of root. )
During querying for root, the parent of those nodes which lie on the path to the root of that queried node will be changed to root. ( All the nodes on the path to root will have the parent as root now.) ( This is called path compression if you don't do this then the query will just return the root and won't change any parent.) Btw, In your code, you have used path compression.
tl;dr
A[i]
always holds the correct root value for the root nodes only. If you wantA[i]
's to hold the correct value then apply queries to all the leaf nodes.