Description

You are an explorer preparing to venture into a mysterious forest filled with rewards and challenges.

The forest is represented as a Binary Tree, where each node is a checkpoint containing a score. Positive scores represent rewards, while negative scores represent penalties.

The forest has a main entrance at the root node (ID = 1). However, your expedition may begin at a different checkpoint, specified by S.

You will explore the region consisting of checkpoint S and all of its descendants.

An ending checkpoint (leaf node) is a checkpoint with no children.

Before starting your adventure, you want to evaluate the rewards and discover the most valuable routes through the forest.

Your task is to implement the following three functions :

1. count_reward_stops(node)

Some checkpoints provide valuable rewards.

Count the number of checkpoints with a positive score in the region starting at node.

• node represents the starting checkpoint of the region.

• A checkpoint is considered a reward stop if its score is strictly greater than 0.

• Include the starting checkpoint and all its descendants.

2. best_expedition(node)

You want to find the most rewarding expedition route.

An expedition begins at the specified checkpoint and follows the forest paths downward until reaching an ending checkpoint.

Find the maximum total score obtainable from such an expedition.

• The expedition must start at node and end at a leaf node.

• At each checkpoint, you may continue to its left or right child, if available.

• The total score includes all checkpoints along the route, including the starting and ending checkpoints.

3. best_crossing_through_start(node)

Some of the forest's most valuable routes connect two different ending checkpoints.

A forest crossing is a path connecting two distinct ending checkpoints. Unlike a regular expedition, a forest crossing may travel upward and downward along the tree connections.

Find the maximum total score of a forest crossing that passes through the starting checkpoint node.

• The crossing must connect a leaf node in the left subtree of node to a leaf node in its right subtree.

• The crossing must pass through the starting checkpoint node.

• The total score includes all checkpoints along the path, with each checkpoint counted exactly once.

• Return the maximum total score of a valid forest crossing.

Important Notes

• All checkpoint scores may be negative.

• The starting checkpoint S may be any node in the tree, not necessarily the root.

• All three functions consider only the subtree rooted at S.

• An expedition must end at a leaf node, even if stopping earlier would produce a higher score.

• A forest crossing must connect two distinct leaf nodes, one in the left subtree and one in the right subtree of S.

• A forest crossing must pass through the starting checkpoint S.

• Each checkpoint along a crossing is counted exactly once.

• The starting checkpoint S is guaranteed to have both a left child and a right child.

Start code

tree = {}

def count_reward_stops(node):
    #TODO
    pass

def best_expedition(node):
    #TODO
    pass

def best_crossing_through_start(node):
    #TODO
    pass

N, S = map(int, input().split())
for _ in range(N):
    node_id, score, left, right = map(int, input().split())
    tree[node_id] = [score, left, right]

print("Positive Checkpoints:", count_reward_stops(S))
print("Max Expedition Score:", best_expedition(S))
print("Max Leaf-to-Leaf Score:", best_crossing_through_start(S))

 

Input

The first line contains two integers, N and S, representing the number of checkpoints and the starting checkpoint.

The next N lines each contain four integers:

node score left right

• node: The ID of the current checkpoint.

• score: The score of the checkpoint.

• left: The ID of its left child, or 0 if there is no left child.

• right: The ID of its right child, or 0 if there is no right child.

The root node always has ID 1, but the starting checkpoint S may be any node in the tree.

The starting checkpoint S is guaranteed to have both a left child and a right child.

Output

Print three lines:

• Reward Stops: X, where X is the number of checkpoints with a positive score in the subtree rooted at S.

• Best Expedition: Y, where Y is the maximum total score along a path from S to a leaf node.

• Best Forest Crossing: Z, where Z is the maximum total score along a path connecting a leaf in the left subtree of S to a leaf in its right subtree.

All checkpoint scores along each path are included exactly once.

Sample Input  Download

Sample Output  Download

Discuss