P10017 [CTT Mutual Test 2023] Axium Crisis

In front of the gloomy tower, Dui Li (pinyin: duì lì) saw a few fragments of light. Those fragments of light lingered around Dui Li like flowers as decoration. Stepping into the twisted maze, Dui Li tried to collect the fragments of conflict inside it, and attempted to destroy this maze. Around Dui Li, fragments of light and conflict were everywhere, flying and crossing. At last, Dui Li reached the deepest part of the maze. On that memory shard with an extremely strange shape, what was reflected was a memory of a world heading toward destruction. The apocalypse arrived: the sky was torn apart, and the earth collapsed. Because the “energy” carried by this shard was far too huge, Dui Li tried to use the surrounding fragments of light and conflict to ease this tremendous mental impact. Specifically, this twisted shard forms a “tree” structure, and Dui Li will place either a light fragment or a conflict fragment on each edge of the tree. Dui Li will cut the edges of this tree into several chains, so that in the end every edge belongs to exactly one chain. Due to the special structure of the shard, a node in the tree can belong to multiple chains at the same time. Dui Li will take some of these chains, merge the prefix segments that have the same placed fragments, and finally form a new tree, the so-called “Trie”. The more nodes this new tree has, the more it can soothe Dui Li’s emotions and help them calm down. In madness, Dui Li has already placed light fragments or conflict fragments on some edges of the shard. In a brief moment of clarity, Dui Li realized something was off. Therefore, Dui Li can still freely choose to place either a light fragment or a conflict fragment on the remaining edges. In a daze, Dui Li found that they did not know how to place and cut in the best way. Thoughts raced rapidly. What is optimal? You surely already have the answer.

You are given a tree with $n$ nodes, numbered $0\sim n-1$. Each edge has a weight. Usually the edge weight is $0$ or $1$, but some edges have an undetermined weight. You need to assign each undetermined edge a weight of $0$ or $1$, and then take several directed paths from the tree such that these chains are pairwise **edge-disjoint**. Then you will insert these paths into a 0/1-Trie, and you want to maximize the number of nodes in this 0/1-Trie (definition of 0/1-Trie omitted). You may need to construct an explicit selection plan.

There are multiple groups of testdata in each test point. The first line contains two integers $T,o$, where $T$ is the number of testdata groups, and $o$ indicates some special properties of this test point (see the description in the “Constraints and Hint” section). Then follow $T$ groups of testdata. For each group, the first line contains an integer $n$, the number of nodes. The next $n-1$ lines each contain three integers $u,v,w$, representing an edge connecting nodes $u$ and $v$. When $0\le w\le 1$, it means the edge weight is $w$; otherwise $w=2$ always holds, meaning the edge weight is not yet determined. It is guaranteed that these edges form a tree on the node set $0\sim n-1$.

At the beginning, output a number $c$ ($c\in\{0,1\}$), indicating whether you choose to output a construction for this test point. We will use a Special Judge to verify whether your output is correct. **Note that this will affect the score upper bound for this test point. See the description in the “Constraints and Hint” section**. For each testdata group, first output one line with a number $A$, the answer for this group. When $c=1$, you also need to continue outputting your constructed plan in the following format: * First output one line with an integer $m$, the number of paths in your plan. * Then output one line with $n-1$ numbers, each being $0$ or $1$, giving the edge weights in the input order. **For edges whose weights are already determined, output them unchanged.** * Then output $m$ lines, each with two numbers $u,v$, representing a path in the tree from $u$ to $v$. You must have $u\neq v$, and the paths must be pairwise **edge-disjoint**.

#### Sample Explanation The answer file corresponding to this sample is: ```plain 8 9 5 16 14 16 15 16 18 ``` The sample output is the `.out` file, which is what you need to output. When $c=1$, you need to construct one valid plan. The sample answer is the `.ans` file. It only provides the answer for each group, and does not provide any construction. Next are the illustrations of these $9$ sample groups (one image before choosing edge weights, and one after).          #### More Samples **Because the data size of this problem is too large, submitting directly for judging will put great pressure on the judging machine. This problem will provide many large samples, so please try to reduce the number of submissions.** For more samples, see the provided files `axiumcrisis*.in/ans`, a total of $20$ groups, basically constructed according to the partial-score approach. Note that the provided answer files **do not give any construction**, and only give the answer for each group. A `checker.cpp` is also provided. You can compile it yourself and run it in a terminal to check validity. For the specific usage, see the description in the “Constraints and Hint” section. The Special Judge used in the official evaluation is not the same as it. To help you understand the statement better, an extra hand-made sample is provided here. This sample is not included in the provided files. **It is recommended to use this sample and the sample explanation to verify your understanding, to avoid misreading.** #### Constraints and Hint Unlike the [version actually used in the mutual test](https://qoj.ac/problem/7769), this problem uses a version with larger constraints. For all data, it is guaranteed that $2\le n\le18$ and $1\le T\le3000$. The distribution of data sizes is shown in the table below. **All subtasks have equal scores, each worth $\rm5pts$ at full score**. A column like $(l,r)$ corresponds to the number of groups with $l\le n\le r$. “Unlimited” means there is no additional restriction. All subtasks are **judged in bundles**: the score of a subtask is the minimum score among its test points. Subtask dependency means the current subtask is judged only if all dependent subtasks have non-zero scores, and the score is also the minimum among the current subtask and its dependent subtasks. The meaning of $o$ will be specified later. |Subtask|$(2,4)$|$(5,6)$|$(7,8)$|$(9,11)$|$(12,14)$|$(15,17)$|$(18,18)$|$o$|Dependencies| |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$1$|$\le1000$|$=0$|$=0$|$=0$|$=0$|$=0$|$=0$|$=0$|None| |$2$|Unlimited|$\le15$|$=0$|$=0$|$=0$|$=0$|$=0$|$=0$|$1$| |$3$|Unlimited|$\le500$|$\le10$|$=0$|$=0$|$=0$|$=0$|$=0$|$2$| |$4$|Unlimited|$\le1000$|$\le50$|$\le10$|$=0$|$=0$|$=0$|$=2$|None| |$5$|Unlimited|$\le1000$|$\le50$|$\le10$|$=0$|$=0$|$=0$|$=3$|None| |$6$|Unlimited|$\le1000$|$\le50$|$\le10$|$=0$|$=0$|$=0$|$=4$|$4$| |$7$|Unlimited|$\le1000$|$\le50$|$\le10$|$=0$|$=0$|$=0$|$=0$|$3,5,6$| |$8$|Unlimited|Unlimited|$\le1000$|$\le60$|$\le10$|$=0$|$=0$|$=2$|$4$| |$9$|Unlimited|Unlimited|$\le1000$|$\le60$|$\le10$|$=0$|$=0$|$=3$|$5$| |$10$|Unlimited|Unlimited|$\le1000$|$\le60$|$\le10$|$=0$|$=0$|$=4$|$6,8$| |$11$|Unlimited|Unlimited|$\le1000$|$\le60$|$\le10$|$=0$|$=0$|$=0$|$7,9,10$| |$12$|Unlimited|Unlimited|Unlimited|$\le300$|$\le30$|$\le10$|$=0$|$=2$|$8$| |$13$|Unlimited|Unlimited|Unlimited|$\le300$|$\le30$|$\le10$|$=0$|$=3$|$9$| |$14$|Unlimited|Unlimited|Unlimited|$\le300$|$\le30$|$\le10$|$=0$|$=4$|$10,12$| |$15$|Unlimited|Unlimited|Unlimited|$\le300$|$\le30$|$\le10$|$=0$|$=0$|$11,13,14$| |$16$|Unlimited|Unlimited|Unlimited|$\le500$|$\le60$|$\le20$|$\le10$|$=1$|None| |$17$|Unlimited|Unlimited|Unlimited|$\le500$|$\le60$|$\le20$|$\le10$|$=2$|$12$| |$18$|Unlimited|Unlimited|Unlimited|$\le500$|$\le60$|$\le20$|$\le10$|$=3$|$13,16$| |$19$|Unlimited|Unlimited|Unlimited|$\le500$|$\le60$|$\le20$|$\le10$|$=4$|$14,16,17$| |$20$|Unlimited|Unlimited|Unlimited|$\le500$|$\le60$|$\le20$|$\le10$|$=0$|$15,18,19$| Next, we explain the special properties described by $o$. * When $o=0$, no special property is guaranteed. * When $o=1$, it is guaranteed that $w=0$ in the input. * When $o=2$, it is guaranteed that $w=2$ in the input. * When $o=3$, it is guaranteed that $w=0$ or $w=1$ in the input. * When $o=4$, it is guaranteed that $w=0$ or $w=2$ in the input. Next, we explain how outputting a construction affects your score. * If you choose $c=0$, then if your answer is correct, you will get $80\%$ of the score for this test point; otherwise you get $0$ for this test point. * If you choose $c=1$, then only when both your answer and your construction are **correct** will you get the full score for this test point; **otherwise you get $0$ for this test point**. So if your construction output might be wrong, please carefully consider switching to not outputting a construction. Next is how to use `checker.cpp`. `checker.cpp` uses a command-line format similar to Testlib, but it is not based on Testlib, so **it does not require the `testlib.h` file**. It is also **compatible with the Lemon format**. Specifically, you can use it as follows: Open a terminal, enter the folder containing `checker.cpp`, and first run `g++ checker.cpp -o checker` to generate the executable (your local compiler should use C++11 or above by default). Suppose the input file is `data.in`, your output file is `data.out`, and the standard answer file is `data.ans`. Put the executable `checker` and the files `data.in/out/ans` in the same folder, then run the following command in the terminal: * If you use Windows, run `checker data.in data.out data.ans 5` in cmd. * If you use Linux, run `./checker data.in data.out data.ans 5` in bash. If you remove the last `5` in the command, it will treat $c=0$ as AC as well. After waiting a moment, it will print the message. If you use Lemon for local judging, you can directly use the executable of `checker.cpp` as the “custom checker” in Lemon. #### Epilogue Watching the apocalyptic scene through the gaps between their fingers, Dui Li swallowed, relying on an unknown kind of courage, and moved their hand away from their face. Dui Li reached out and took in the end of the world, storing it among the countless memories they had collected. The rest of the tragic memories seemed not worth mentioning under the reflection of this shard. Dui Li was sure they had become strong enough, and naturally wanted to destroy everything at once. Thus, along with that sincere smile and weary laughter, Dui Li descended from the sky to the ground. Driven by such power, that ancient tower gradually fell. And Dui Li, holding firm to a hero-like belief, kept moving forward without hesitation. Translated by ChatGPT 5