Why is this a WA for PSHTTR?

I wrote this code and made many changes and submitted it many times but never got an AC even for the smaller case. Please help me find the error. Here’s my code:

import queue 
 
cases = int(input())
 
class Node:
    array = []
    def __init__(self, index, parent, weight):
        self.index = index
        self.parent = parent
        self.weight = weight
        self.ancestors = []
        self.height = 0
            
        Node.array.append(self)
 
    def initialize(self):
        if self.parent == None:
            self.ancestors = [self.index]
            self.height = 0
            
        else:
            mother = Node.array[self.parent]
            self.ancestors = mother.ancestors[:]
            self.ancestors.append(self.index)
            self.height = mother.height + 1
 
for _ in range(cases):
    vertices = int(input())
 
    root = Node(0, None, 0)
    root.initialize()
 
    to_init = queue.Queue(maxsize=100000)
 
    for vertex in range(vertices - 1):
        parent, node, weight = input().split()
        parent, node, weight = int(parent) - 1, int(node) - 1, int(weight)
        to_init.put(node)
 
        Node(node, parent, weight)
 
    Node.array = sorted(Node.array, key=lambda x: x.index)
    
    while not (to_init.empty()):
        index = to_init.get()
        Node.array[index].initialize()
 
    queries = int(input())
 
    for query in range(queries):
        u, v, limit = input().split()
        u, v, limit = int(u) - 1, int(v) - 1, int(limit)
        
        start = Node.array[u]
        dest = Node.array[v]
 
        height = min(start.height, dest.height)
        xor = 0
 
        for h in range(height - 1, 0, -1):            
            if start.ancestors[h] == dest.ancestors[h]:
                break
 
            if Node.array[start.ancestors[h]].weight <= limit:
                xor ^= Node.array[start.ancestors[h]].weight
                
            if Node.array[dest.ancestors[h]].weight <= limit:
                xor ^= Node.array[dest.ancestors[h]].weight
 
        for point in start.ancestors[height:] + dest.ancestors[height:]:
            weight = Node.array[point].weight
            if weight <= limit:
                xor ^= weight
 
        print(xor)
 
    Node.array = list()
1 Like

Your code has a very simple bug. Run your code for this test case-

Input
1
10
1 2 50
3 2 5
4 2 7
4 5 10
2 6 8
6 7 15
1 8 37
4 9 23
6 10 47
2
9 1 37
5 3 100
Your Output
23
10
Correct Output
16
8

The reason of your WA is here-

for vertex in range(vertices - 1):
        parent, node, weight = input().split()
        parent, node, weight = int(parent) - 1, int(node) - 1, int(weight)
        to_init.put(node)

Why assume that first vertex is always parent? I can give input as-

4
1 2
1 3
1 4
//Code runs fine here
OR
4
2 1
3 1
4 1
//Your code messes up here
1 Like

Please help me with this.

@vijju123 How can I get rid of this error? I’ll have to check if any of the two nodes are already defined which would take O(n) additionally. Should I re-implement the solution in C++ and use pointers?

Also, by the way I couldn’t find a single Python all-correct solution for the above problem. I think I’ll need to use C++.

Check my solution, i used the same concept, with a little bit of tweaking. https://www.codechef.com/viewsolution/14561376