Maximizing 0/1-Trie Nodes from Tree Paths

You are given a tree with n nodes numbered from 0 to n-1. The tree has n-1 edges. Each edge carries a weight that is either \(0\) or \(1\), but some edges have an undetermined weight (represented as \(-1\) in the input). You are allowed to assign each undetermined edge a weight of \(0\) or \(1\>.

After assigning weights, you must select a set of directed paths in the tree such that no two selected paths share a common edge (i.e. they are edge-disjoint). For each chosen path, read the weights of its edges (in the chosen traversal order) and interpret them as a binary string. These binary strings are then inserted into a 0/1-Trie (binary trie), where each node corresponds to a prefix shared by some of the strings. Thus, the total number of nodes in the trie is \(1+\) (the number of distinct nonempty prefixes inserted).

Your task is to determine the maximum possible number of nodes that can appear in the 0/1-Trie by choosing an optimal assignment for undetermined edge weights and an optimal set of edge-disjoint paths. Note that the orientation of a path is up to you. In particular, if the first edge of a chosen path has a forced (fixed) weight then that digit is predetermined, but if it is undetermined you may later assign it appropriately. When selecting two paths, if both have their first edge weight forced then they must be different (i.e. one must be \(0\) and the other \(1\)) so that the two binary strings have different first digits and therefore do not share the first child node of the trie.

Input Format: The first line contains an integer \(n\), the number of nodes. Each of the following \(n-1\) lines contains three space‐separated integers \(u\), \(v\), and \(w\), indicating an edge between nodes \(u\) and \(v\) with weight \(w\). Note that \(w = -1\) indicates that the weight is undetermined.

Output Format: Output a single integer representing the maximum number of nodes in the 0/1-Trie that can be obtained.

inputFormat

The first line contains an integer \(n\) (the number of nodes). The following \(n-1\) lines each contain three space-separated integers \(u\), \(v\), and \(w\). Here, \(w = -1\) indicates that the weight of that edge is undetermined.

outputFormat

Output a single integer: the maximum number of nodes in the 0/1-Trie obtainable under an optimal assignment of undetermined weights and an optimal selection of edge-disjoint directed paths (with appropriate orientation choices).

sample

4
0 1 -1
0 2 0
0 3 -1

4