Nowcoder problem: Game on Tree

Правка en2, от Aveiro_quanyue, 2023-05-15 13:47:57

Alice and Bob are playing a game on a tree $$$T$$$ whose root is $$$1$$$. $$$T$$$ has $$$n$$$ vertices and $$$n-1$$$ edges, each vertex has an attribute $$$a \in \{1,2,3\}$$$. If $$$a=1$$$, a person on this vertex $$$v$$$ must jump to the parent of $$$v$$$, i.e., $$$v->parent$$$. If $$$a=2$$$, a person on this vertex $$$v$$$ must jump to $$$v$$$'s grandparent, i.e., $$$v->parent->parent$$$. If $$$a=3$$$, a person on this vertex can either jump to $$$v->parent$$$ or $$$v->parent->parent$$$. Alice starts the first. If somebody cannot make a move, she/he loses the game. For example, if Alice stands on a child of the root and this child has attribute $$$2$$$, then Alice loses as this child does not have a grandparent. Similarly if Bob stands on the root, he will lose as he cannot move no matter what the attribute of the root is.

Input contains $$$n+1$$$ lines.

The first line contains a single integer $$$n$$$, which is the number of vertices.

The

Теги tree, graph, game theory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en16 Английский Aveiro_quanyue 2023-05-15 14:29:27 6
en15 Английский Aveiro_quanyue 2023-05-15 14:26:17 9 Tiny change: 'd edge of the tree $T$.\n\nO' -> 'd edge of $T$.\n\nO'
en14 Английский Aveiro_quanyue 2023-05-15 14:25:37 0 (published)
en13 Английский Aveiro_quanyue 2023-05-15 14:25:15 15
en12 Английский Aveiro_quanyue 2023-05-15 14:23:46 40
en11 Английский Aveiro_quanyue 2023-05-15 14:22:55 53 Tiny change: 'Alice and ' -> 'Link: https://ac.nowcoder.com/acm/contest/56458/E\n\nAlice and '
en10 Английский Aveiro_quanyue 2023-05-15 14:22:41 9 Tiny change: 'eger $n$, which is the numbe' -> 'eger $n$, the numbe'
en9 Английский Aveiro_quanyue 2023-05-15 14:22:25 5
en8 Английский Aveiro_quanyue 2023-05-15 14:21:37 1397
en7 Английский Aveiro_quanyue 2023-05-15 14:08:31 64
en6 Английский Aveiro_quanyue 2023-05-15 14:06:45 353
en5 Английский Aveiro_quanyue 2023-05-15 14:00:56 760
en4 Английский Aveiro_quanyue 2023-05-15 13:56:50 118
en3 Английский Aveiro_quanyue 2023-05-15 13:54:59 671
en2 Английский Aveiro_quanyue 2023-05-15 13:47:57 831
en1 Английский Aveiro_quanyue 2023-05-15 13:40:41 91 Initial revision (saved to drafts)