Directed Tree Reachability

This is an interactive-style problem turned into a non‐interactive simulation. You are given a tree of n nodes (numbered from 1 to n) with n-1 transportation channels. Each channel was installed with an initial direction: from u to v. However, each channel is controlled by a switch which can flip its direction. In particular, if the switch is at position 0, the channel works in the original direction (from u to v), and if set to 1, the channel’s direction is reversed (from v to u).

The central monitor reports, for every node, the number of distinct nodes (including itself) that are able to transport ore to that node via a sequence of channels (i.e. there exists a directed path from that node to the destination). Your task is, given the final configuration (after all switches have been set), to compute for every node the number of nodes from which ore can be transported to it.

Note on the interactive flavour: In the original interactive version you could change the switches and wait for the readings (with at most 50 readings allowed). For this problem, the final configuration is given as input and you simply need to output the monitor readings.

Important: All formulas should be written in \( \LaTeX \) format. For example, the number of nodes is denoted as \( n \), and the nodes are numbered \( 1 \sim n \). An edge from \( u \) to \( v \) when the switch is at 0 is written as \( u \to v \), and when flipped (switch at 1) it becomes \( v \to u \).

inputFormat

The input begins with an integer \( n \) \( (2 \le n \le 10^5) \) representing the number of nodes in the tree. This is followed by \( n-1 \) lines. Each of these lines contains three integers \( u\), \( v \), and \( s \) \( (s \in \{0,1\}) \). Here, \( u \) and \( v \) denote the endpoints of a transportation channel, and \( s \) is the state of the corresponding switch:

• If \( s = 0 \), the channel is directed from \( u \) to \( v \) (i.e. \( u \to v \)).
• If \( s = 1 \), the channel is directed from \( v \) to \( u \) (i.e. \( v \to u \)).

outputFormat

Output \( n \) lines. The \( i\)-th line should contain a single integer representing the number of distinct nodes which can send ore to node \( i \) (including node \( i \) itself). In other words, for each node \( i \), count the number of nodes \( r \) such that there is a directed path from \( r \) to \( i \).

sample

2
1 2 0

1
2