[Problem proposal] Unionfind with Potential

[Misuki743]

Problem name: Unionfind with Potential

Problem

Given a graph with $N$ vertices and $0$ edges, each vertex have some weight $w_v$ on it. Process the following $Q$ queries in order:

• $t_i = 0 \text{ } u_i \text{ } v_i \text{ } d_i$: Add an edge $(u_i, vi)$ with constraint $w{vi} - w{u_i} = d_i$
• $t_i = 1 \text{ } u_i \text{ } vi$: Print $w{vi} - w{u_i}$

Solution

Maintain difference of $wv$ and $w{p_v}$ in Unionfind.

Constraint

• $2 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• The graph is a forest at any time
• $u_i, v_i$ in query of type 2 would belong to same connect component at that time

Note / Disucussion

• Do we need to consider something more general instead of $w_{vi} - w{u_i}$?
• Do we need to consider the case where edges may form cycles and report when contradiction happen?

[maspypy]

Thank you! Since this data structure can handle groups (not limited to commutative groups), I want to deal with non-commutative groups. Here are some examples of the types of problems we can consider:

Each vertex has values $(x[0], \ldots, x[N-1])$. These values are unknown.

[Query 1] Given $(u, v, a, b)$, where $a \neq 0$. This means the information $x[v] = a x[u] + b \pmod{998244353}$. This information is valid if it does not contradict any previously valid information. Output whether this information is valid or invalid.

[Query 2] Given (u, v, x). Based on the previously valid information and assuming x[u] = x, determine x[v] or print -1 if it can't be determined.

[Misuki743]

Seems nice, but to compute the inverse of affine would require computation of modulo inverse, which would make the time complexity increase from $O(q \alpha(n))$ to $O(q (\alpha(n) + \lg \text{mod}))$, maybe it's better to find a way to avoid extra cost not from the data structure itself? For example, change to another non-commutative group whose inverse won't be that costly, or just gives affine and its inverse in the input?