i've read the tutorial for this problem over 30 times and looked at many codes and it still doesnt make sense , why are we using dsu ? how does adding an edge between node a and b with weight c determine all the values on the simple path from a to b ?

if somebody had solved it i would appreciate it if u write an explanation

1615D - X(or)-mas Tree

given a modular equation k = ax mod b where we know k and a and b find the smallest possible integer number for x

example (15 = 8x mod 25) , here the set of x that satisfy it up to the smallest integer are [1.875 , 3.75 , 5] but the smallest integer number is 5 how do i find the smallest integer number that satisfies the equation in o(1) or o(logb) anything thats not o(b) and above

searched alot and all i was able to find is the usage of EEX but i dont think its what iam looking for also modular inverse doesnt necessarily work since b (the mod) might not coprime with a or k

i was reading the tutorial for problem E from this round https://mirror.codeforces.com/blog/entry/125943

and it says that "And as it is known, the number of edges in the compressed tree is O(k)"

i couldnt find anything about it on the internet does anyone have a proof on why we have O(k) edges in a compressed tree ?

edit : i realized how stupid i was asking this question since we can have atmost 2k — 1 vertices in a compressed tree (where k is the number of important vertices in the main tree) there can be at most 2k — 2 edges since a tree will always have n — 1 edges

how would you write a checker for problem B from the contest Think-cell round 1 with complexity less than n^2 ?

in others words given a permutation of size n determine weather there exists 2 indices i and j (1 <= i,j <n) i != j , where p(i) devides p(j) and p(i+1) devides p(j+1)