Implementing a recursive algorithm for tree.

[Negativ3]

I'm trying to solve

You are given a rooted tree with N nodes (numbered 1 through N); node 1 is the root. Each node has a value; let's denote the value of node i by Ai.

You may perform the following operation any number of times (including zero): choose any node which still exists in the tree and remove the whole subtree of this node including itself.

Let's define the profit as the sum of values of all nodes which currently exist in the tree minus X⋅k, where k denotes the number of times this operation was performed. Find the maximum possible profit.

Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and X.
The second line contains N space-separated integers A1,A2,…,AN.
Each of the following N−1 lines contains two space-separated integers u and v denoting that nodes u and v are connected by an edge.
Output
For each test case, print a single line containing one integer — the maximum profit.

Constraints
1≤T≤10
1≤N≤105
1≤X≤109
1≤u,v≤N
|Ai|≤109 for each valid i
the graph described on the input is a tree
Subtasks
Subtask #1 (30 points): 1≤N≤1,000
Subtask #2 (70 points): original constraints

Example Input
1
3 5
1 -5 -10
1 2
2 3
Example Output
-4

here is what I came up with.

class Node:
    def __init__(self, identifier):
        self.__identifier = identifier
        self.__children = []

    @property
    def identifier(self):
        return self.__identifier

    @property
    def children(self):
        return self.__children

    def add_child(self, identifier):
        self.__children.append(identifier)

(_ROOT, _DEPTH, _BREADTH) = range(3)


class Tree:

    def __init__(self,x):
        self.__nodes = {}
        self.x = x

    @property
    def nodes(self):
        return self.__nodes

    def add_node(self, identifier, parent=None):
        node = Node(identifier)
        self[identifier] = node

        if parent is not None:
            self[parent].add_child(identifier)

        return node

    def display(self, identifier, depth=_ROOT):
        children = self[identifier].children
        if depth == _ROOT:
            print("{0}".format(identifier))
        else:
            print("\t"*depth, "{0}".format(identifier))

        depth += 1
        for child in children:
            self.display(child, depth)  # recursive call

    def traverse(self, identifier, mode=_DEPTH):
        # Python generator. Loosly based on an algorithm from 
        # 'Essential LISP' by John R. Anderson, Albert T. Corbett, 
        # and Brian J. Reiser, page 239-241
        yield identifier
        queue = self[identifier].children
        while queue:
            yield queue[0]
            expansion = self[queue[0]].children
            if mode == _DEPTH:
                queue = expansion + queue[1:]  # depth-first
            elif mode == _BREADTH:
                queue = queue[1:] + expansion  # width-first
    def max_profit(self,identifier):

        return max(-x,self[identifier] + sum(map(max_profit, self[identifier].children)))
    def __getitem__(self, key):
        return self.__nodes[key]

    def __setitem__(self, key, item):
        self.__nodes[key] = item



for i in range(int(input())):
    n,x = map(int,input().split())
    weight = list(map(int,input().strip().split()))
    summ = sum(weight)
    sumWeight = summ
    dic = dict()
    tree = Tree(x)
    tree.add_node(weight[0])
    for i in range(n-1):
        a,b = map(int,input().split())

        if a not in dic.keys():
            dic[weight[a-1]] = weight[b-1]
        else:
            dic[weight[a-1]].append(weight[b])
        if b not in dic.keys():
            dic[weight[b-1]] = weight[a-1]
        else:
            dic[weight[b-1]].append(weight[a-1])
        tree.add_node(weight[b-1],weight[a-1])
    print(dic)
    for i in tree.traverse(1,_BREADTH):
        print(i)
    y = tree.max_profit(1)
    print(y)

I'm not familiar with OOP's so,
What I need is to make the max_profit function work.
Any help will be appreciate.

[Yoriz]

Could you explain what is currently wrong with the max_profit function, what do you expect it to do, what does it do, is there an error if so post full error in error code tags please.

[Negativ3]

Hi Thanks for replying,
I'm learning how to use BBcode
I can't make the max_profit function to work,
The map is giving problem, It was supposed to take a function as a first argument and iterable as another,
but Its giving a error as:

Error:
Traceback (most recent call last):
  File "f:\coding n stuffs\asdfasda.py", line 97, in <module>
    y = tree.max_profit(1)
  File "f:\coding n stuffs\asdfasda.py", line 65, in max_profit
    return max(-x,self[identifier] + sum(map(max_profit, self[identifier].children)))
NameError: name 'max_profit' is not defined

PS F:\coding n stuffs>

sorry for not formatting I'm going through the help page to learn bbcode.

[Yoriz]

There isn't a max_profit function only the max_profit method of the Tree class, that is why it is saying its not defined.