P4228 [Tsinghua Training 2017] Heart of the Banyan Tree

Late autumn. The cold wind has blown away the last trace of summer heat and the leaves of the bushes under the banyan tree. Evan and Lyra, who have known each other for years, have returned once again to the lush banyan tree where they met as children. The brook is the same, the stone bridge is the same; though the banyan tree has experienced cycles of thriving and withering, it still stands tall like a green canopy. Only Evan and Lyra are no longer the inexperienced teenagers they were seven or eight years ago. ... “It’s almost winter, yet the banyan still hasn’t shed its leaves...” “The banyan is an evergreen; you won’t see a distinct season of leaf fall...” “Sigh... I didn’t expect it’s already been seven years. The banyan is the same as it was back then, but you are no longer who you were...” “Is there really anything that never changes? The banyan is evergreen, and its seemingly everlasting green canopy is made up of countless leaves cycling through life and death. In the passage of time, everything is constantly changing...” “But look at this banyan—day after day, season after season, year after year—it seems unchanged since ancient times, with gnarled roots and lush foliage. I’m thinking, perhaps it would be better to be a tree, letting time flow between my branches and leaves, while I simply keep this patch of shade.” “The banyan may endure, but in this infinite span of time, it will eventually return to dust. Rather than rooting in one place and experiencing the same seasonal cycle year after year like a banyan, why not see as much of the world as possible in limited time? Besides, although the banyan grows slowly, it still sends out a new branch each spring to explore outward...” “Really? Over its long life, the banyan explores step by step like that?” “Even if the canopy appears unchanged, the banyan follows periodic changes over time. When spring comes, it naturally grows; it should show that, shouldn’t it...” “Compared to instinctive growth in response to the seasons, I’d rather believe the banyan has a lively, exploring heart.” “In fact, the banyan does have a heart. When it’s first planted, the heart sprouts at the root. Later, each spring when the banyan grows a new branch, its heart moves a little toward the direction of that new branch, getting closer to the outside world. Look at the branches above your head—crisscrossing in all directions—the heart has been moving among these boughs for decades...” “Wow, so somewhere among this dense network of branches, the banyan’s heart is hidden?” “Exactly. But to know where it is, you’ll need to put in some extra effort...” “Ah, thinking about it, a tree still isn’t as good as a person... For example, you—if you lean in like this, you can hear the heartbeat...” ...

A banyan can be abstracted as a rooted tree with $n$ nodes, numbered $1 \sim n$, where node $1$ is the root. Initially, the tree has only node $1$, and the heart is at node $1$. After that, at each step, the tree grows a new node: specifically, a node adjacent to some currently existing node is added to the tree. Then, the heart moves one step along the simple path from the heart to the newly added node. This tree with $n$ nodes has many possible growth orders, and different orders may lead to different final positions of the heart. Now Evan and Lyra want to know: which nodes could possibly be the final resting position of the heart when the growth process ends? For example, consider a tree of size $4$ with edges $\{,,\}$. There are three different growth orders that make the heart end at nodes $2$, $3$, and $4$, respectively: Finally ending at node $2$: - Grow $3$ from $1$, the heart moves from $1$ to $3$, - Grow $4$ from $1$, the heart moves from $3$ back to $1$, - Grow $2$ from $1$, the heart moves from $1$ to $2$. Finally ending at node $3$: - Grow $2$ from $1$, the heart moves from $1$ to $2$, - Grow $4$ from $1$, the heart moves from $2$ back to $1$, - Grow $3$ from $1$, the heart moves from $1$ to $3$. Finally ending at node $4$: - Grow $2$ from $1$, the heart moves from $1$ to $2$, - Grow $3$ from $1$, the heart moves from $2$ back to $1$, - Grow $4$ from $1$, the heart moves from $1$ to $4$. We can prove that there is no growth order that makes the heart end at node $1$.

Read from standard input. The first line contains two positive integers $W, T$, representing the subtask identifier (in the samples $W = 0$) and the number of test cases. Then follow $T$ test cases. For each test case: - The first line contains a positive integer $n$, the number of nodes in the tree. - The next $n - 1$ lines each contain two positive integers $a_i, b_i$, indicating there is a tree edge between nodes numbered $a_i$ and $b_i$. It is guaranteed that $a_i \neq b_i$ and the $n - 1$ edges form a tree.

Output to standard output. If the input $W$ is not equal to $3$, for each test case output a line containing a length-$n$ $01$ string. The $i$-th character indicates whether node $i$ could be the final position of the heart. A $1$ means possible, and a $0$ means impossible. If the input $W$ equals $3$, then for each test case output a single character indicating the answer for node $1$.

TestPoint 1 [10 pts] - $T \leq 50; n \leq 15$. TestPoint 2 [10 pts] - $T \leq 20; n \leq 10^5$. For every node except node $1$, the degree (including its parent) is at most $2$. TestPoint 3 [10 pts] - $T \leq 200; n \leq 100$. Only output a single character indicating the answer for node $1$, i.e., it suffices to ensure the correctness for node $1$. TestPoint 4 [35 pts] - $T \leq 20; n \leq 10^3$. TestPoint 5 [35 pts] - $T \leq 20; n \leq 10^5$. Translated by ChatGPT 5