Contact Form Submission - Request - Missing Section or Solution (Problem Solution - Vertex Add Component Sum (ID: ys-VertexAddComponentSum))

[maggieliu05]

Someone submitted the contact form!

URL: https://usaco.guide/problems/ys-VertexAddComponentSum/user-solutions
Module: Problem Solution - Vertex Add Component Sum (ID: ys-VertexAddComponentSum)
Topic: Request - Missing Section or Solution
Message:
Can you guys please add a more detailed solution to this problem? The user solution seems a bit difficult to grasp. Thanks a lot and keep doing the amazing work!

[SansPapyrus683]

@brebenelmihnea u up for this?

[brebenelmihnea]

@SansPapyrus683 Yep

[ghost]

For this problem I've tried to code a solution in Python:
Pls check to see if it is right & easy to understand

class PersistentDisjointSet:
def init(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.value = [0] * n

def find(self, v, time):
    if self.parent[v] == v:
        return v
    return self.find(self.parent[v], time) if time >= self.value[v] else v

def union(self, u, v, time):
    u = self.find(u, time)
    v = self.find(v, time)
    if u != v:
        if self.rank[u] < self.rank[v]:
            u, v = v, u
        self.parent[v] = u
        if self.rank[u] == self.rank[v]:
            self.rank[u] += 1

def add_edge(self, u, v, time):
    self.union(u, v, time)

def remove_edge(self, u, v, time):
    self.union(u, v, time - 1)

def update_value(self, v, x):
    self.value[v] += x

def query(self, v, time):
    root = self.find(v, time)
    total = 0
    for i in range(len(self.parent)):
        if self.find(i, time) == root:
            total += self.value[i]
    return total

Example usage

N = 10 # Number of vertices
Q = 5 # Number of queries

dsu = PersistentDisjointSet(N)

Process queries

queries = [(0, 1, 2), (2, 3, 10), (0, 2, 4), (3, 2, 5), (3,)]
for query in queries:
if query[0] == 0:
dsu.add_edge(query[1], query[2], len(queries))
elif query[0] == 1:
dsu.remove_edge(query[1], query[2], len(queries))
elif query[0] == 2:
dsu.update_value(query[1], query[2])
elif query[0] == 3:
result = dsu.query(query[1], len(queries))
print(result)

[SansPapyrus683]

could you format your code correctly

[ghost]

class DSU:
def init(self, n):
self.parent = list(range(n))
self.size = [1] * n
self.value = [0] * n

def find(self, u):
if self.parent[u] == u:
return u
self.parent[u] = self.find(self.parent[u])
return self.parent[u]

def union(self, u, v):
root_u = self.find(u)
root_v = self.find(v)
if root_u != root_v:
if self.size[root_u] < self.size[root_v]:
root_u, root_v = root_v, root_u
self.parent[root_v] = root_u
self.size[root_u] += self.size[root_v]
self.value[root_u] += self.value[root_v]

N = int(input())
values = list(map(int, input().split()))

dsu = DSU(N)

for _ in range(Q):
query = list(map(int, input().split()))
if query[0] == 0:
u, v = query[1], query[2]
dsu.union(u, v)
elif query[0] == 1:
u, v = query[1], query[2]
root_u = dsu.find(u)
root_v = dsu.find(v)
if root_u == root_v:
dsu.value[root_u] -= (values[u] + values[v])
elif query[0] == 2:
v, x = query[1], query[2]
root_v = dsu.find(v)
dsu.value[root_v] += x
elif query[0] == 3:
v = query[1]
root_v = dsu.find(v)
print(dsu.value[root_v])

[SansPapyrus683]

uh it's still not formatted correctly 💀

[ghost]

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.value = [0] * n

    def find(self, u):
        if self.parent[u] == u:
            return u
        self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            if self.size[root_u] < self.size[root_v]:
                root_u, root_v = root_v, root_u
            self.parent[root_v] = root_u
            self.size[root_u] += self.size[root_v]
            self.value[root_u] += self.value[root_v]

N = int(input())
values = list(map(int, input().split()))

dsu = DSU(N)

Q = int(input())

for _ in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 0:
        u, v = query[1], query[2]
        dsu.union(u, v)
    elif query[0] == 1:
        u, v = query[1], query[2]
        root_u = dsu.find(u)
        root_v = dsu.find(v)
        if root_u == root_v:
            dsu.value[root_u] -= (values[u] + values[v])
    elif query[0] == 2:
        v, x = query[1], query[2]
        root_v = dsu.find(v)
        dsu.value[root_v] += x
    elif query[0] == 3:
        v = query[1]
        root_v = dsu.find(v)
        print(dsu.value[root_v])

[bqi343]

very late, but if you want to add your own code to the internal solution, please follow the instructions at https://usaco.guide/general/adding-solution#steps @TheScarletPhoenix

[SansPapyrus683]

moved to #4165