$$$\bf{D1T1\ Gray\ Code\ 1s\ 256MB}$$$

$$$\bf{Statement}$$$

Gray Code is a special permutation of $$$n$$$-bit binary strings ,which requires adjacent strings have exactly one different bit. Specially, the first string is adjacent to the last string.

One example of $$$2$$$-bit Gray Code is $$$00,01,11,10$$$.

We give an algorithm of generating Gray Code below:

• $$$1.$$$ $$$1$$$-bit Gray Code consist of two $$$1$$$-bit binary string: $$$0,1$$$

• $$$2.$$$ The first $$$2^n$$$ binary strings of $$$(n+1)$$$-bit Gray Code is $$$n$$$-bit Gray Code($$$2^n$$$ binary strings in total) generated by this algorithm adding a prefix $$$0$$$.

• $$$3.$$$ The next $$$2^n$$$ binary strings of $$$(n+1)$$$-bit Gray Code is $$$n$$$-bit Gray Code($$$2^n$$$ binary strings in total) generated by this algorithm being reversed ,then adding a prefix $$$1$$$.

We number all the Gray Code from $$$0$$$ to $$$2^n-1$$$. Now you task is to figure out the $$$k$$$-th binary string of $$$n$$$-bit Gray Code.

$$$\bf{Input}$$$

Only two integer $$$n ,k$$$ ,the bit of Gray Code and the index of the binary string.

$$$\bf{Output}$$$

One binary string, the answer.

$$$\bf{Constraints}$$$

$$$1\le n \le 64, 0\le k < 2^n$$$

$$$\bf{D1T2\ Brackets\ Tree\ 1s\ 256MB}$$$

$$$\bf{Statement}$$$

First we have some definitions in this problem.

What is a valid bracket string:

• $$$1.$$$ $$$()$$$ is;
• $$$2.$$$ If $$$A$$$ is, then $$$(A)$$$ is;
• $$$3.$$$ if $$$A$$$ and $$$B$$$ are, then $$$(AB)$$$ is.

What are a substring and different substrings:

• $$$1.$$$ The substring of string $$$S$$$ is a string consisting of any continuous characters in string $$$S$$$. We can describe a substring like $$$S(l,r)\ (1 \le l \le r \le |S| ,|S|$$$ is the length of string $$$S$$$)​ , where $$$l$$$ and $$$r$$$ are the left endpoint and right endpoint, respectively.
• $$$2.$$$ Two substrings of string $$$S$$$ is regarded different when they have different $$$l$$$ or $$$r$$$.

A tree consists of $$$n$$$ vertices and $$$n-1$$$ edges. Every edge connects two vertices. There is exactly one simple path between two vertices on a tree.

Little Q is a curious kid. One day on his way to school he saw a tree consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. The vertex with index $$$1$$$ is the root. Except vertex $$$1$$$, every vertex has one parent. The parent of vertex $$$u$$$ is $$$f_u\ (1 \le f_u < u)$$$.

Little Q found that there was exactly one bracket on a vertex. It could be $$$'('$$$ or $$$')'$$$. Little Q defined $$$s_i$$$ as the string formed by: writing down all the vertices through the simple path from root to vertex $$$i$$$ in one line.

It is obvious that $$$s_i$$$ is a bracket string but may not be a valid bracket string. So Little Q was going to figure out, for every $$$i\ (1 \le i \le n)$$$, how many different substrings of $$$s_i$$$ are valid bracket string?

This problem is so difficult for Little Q, so he wants you to help him out. Denote $$$k_i$$$ is the number of valid bracket string in different substrings of $$$s_i$$$. You need to figure out $$$\bigotimes\limits^{n}_{i=1} i\times k_i$$$. $$$\bigotimes$$$ stands for $$$\bf{xor}$$$ operation here.

$$$\bf{Input}$$$

The first line contains one integer $$$n$$$, the number of vertices on the tree.

The second line contains one string consisting of characters $$$'(’$$$ and $$$')'$$$ (No quotation marks). The $$$i$$$-th bracket is the bracket on $$$i$$$-th vertex.

The next $$$n-1$$$ lines contains all the edges on the tree.

$$$\bf{Output}$$$

One integer, the answer.

$$$\bf{Constrains}$$$

$$$1 \le n \le 5\times 10^5$$$

$$$\bf{D1T3\ Numbers\ on\ a\ Tree\ 2s\ 256MB}$$$

$$$\bf{Statement}$$$

You are given a tree consisting of $$$n$$$ vertices and $$$n-1$$$ edges. Vertices are numbered from $$$1$$$ to $$$n$$$. At the beginning, every vertex has a different number on it. Numbers are $$$1,2,...,n$$$.

Next, you are going to cut off exactly $$$n-1$$$ edges. During one operation, you choose a edge connecting vertex $$$u ,v$$$, exchange each number on itself, then the edge disappears.

After $$$n-1$$$ operations, all the edges are cut off. Now sort all the vertices by number on it, from small to large. Then you get a permutation $$$P_i$$$ of the vertices. Your goal is to minimize the lexicographical order of $$$P_i$$$.

$$$\bf{Input}$$$

Input contains several testcases.

The first line contains an integer $$$T$$$, the number of testcases.

For every testcases:

The first line contains an integer $$$n$$$, the number of vertices.

The second line contains $$$n$$$ integers, the $$$i$$$-th integer is the index of the vertex on which number $$$i$$$ is at beginning.

The next $$$n-1$$$ lines contains all the edges on the tree.

$$$\bf{Output}$$$

For every testcase:

Output $$$n$$$ integers separated by space, the minimum lexicographical order of permutation $$$P_i$$$.

$$$\bf{Constraints}$$$

$$$1 \le T \le 10 ,1 \le n \le 2000$$$

$$$\bf{D2T1\ Today's\ Meal\ of\ Emiya's\ 1s\ 256MB}$$$

$$$\bf{Statement}$$$

Emiya is a high school student. He is good at cooking. He masters $$$n$$$ ways of cooking and has $$$m$$$ kinds of different ingredients. We number cooking ways from $$$1$$$ to $$$n$$$ and ingredients from $$$1$$$ to $$$m$$$.

Every dish Emiya makes will use exactly one cooking way and exactly one ingredient. If he use $$$i$$$-th cooking way and $$$j$$$-th ingredient, then he can make $$$a_{i,j}$$$ different dishes, which means Emiya can make $$$\sum\limits^{n}_{i=1}\sum\limits^{m}_{j=1}a_{i,j}$$$ different dishes in total.

Today Emiya is going to make a meal for his friend Yazid and Rin. They all have their own needs. For a meal with $$$k$$$ dishes:

• Emiya does not want to make themselves hungry, so $$$k\ge 1$$$.
• Rin wants to try different cooking ways, so every dishes must use different cooking ways.
• Yazid does not want to taste many dishes made of the same ingredient, so all the ingredients can be used in at most $$$\left\lfloor \frac{k}{2}\right\rfloor$$$ dishes.

$$$\left\lfloor x\right\rfloor$$$ here means the minimum integer that is equal or less than $$$x$$$.

Their needs is easy to realize for Emiya, so he tries to figure out how many ways there are to make a meal? Two meals are different when they have at least one different dish.

Emiya finds you. You should help him calculate the number of ways modulo $$$998,244,353$$$

$$$\bf{Input}$$$

The first line contains two integer $$$n,m$$$, the number of cooking ways and the number of different ingredients.

In the next $$$n$$$ lines ,the $$$j$$$-th number of $$$i$$$-th line is $$$a_{i,j}$$$, the different dishes Emiya can make when using $$$i$$$-th cooking way and $$$j$$$-th ingredient.

$$$\bf{Output}$$$

One integer, the answer modulo $$$998,244,353$$$.

$$$\bf{Constraints}$$$

$$$1 \le n \le 100 ,1 \le m \le 2000 ,0 \le a_{i,j} < 998,244,353$$$

$$$\bf{D2T2\ Partition\ 2s\ 1GB}$$$

$$$\bf{Statement}$$$

In 2048, in the exam hall of The 48th CSP, contestant Little Ming is looking at the first problem. The sample has $$$n$$$ testcases numbered from $$$1$$$ to $$$n$$$. The scale of $$$i$$$-th testcase is $$$a_i$$$.

Little Ming does a brute-force solution. His program needs $$$u^2$$$ seconds to solve a testcases with $$$u$$$ scale. However, after running on a testcases with $$$u$$$ scale, the program will get RE on any testcases with scale strictly less than $$$u$$$. In the sample, $$$a_i$$$ is not always increasing. Little Ming wants to get AC on the sample without reprogramming ,so he use a very natural way: combining some adjacent testcases. The new scale of some combined testcases is the sum of scale of these testcases.

Formally, Little Ming needs to find out some borders $$$1 \le k_1 < k_2 < ... <k_p \le n$$$, making:

When $$$p = 0$$$, it means Little Ming combines all testcases together.

Little Ming does not want to get RE or TLE, so he wants to minimum his program's running time, which means minimizing:

Little Ming loves the problem very much, so he writes this problem and ask you: with given $$$n$$$ and $$$a_i$$$, how to figure out the minimum running time?

$$$\bf{Input}$$$

To avoid much input time, some testcases will be generated in contestants' program.

The first line contains two integer $$$n,type$$$ ,the number of "testcases" and the way of inputting.

• $$$1.$$$ If $$$type = 0$$$, $$$a_i$$$ will be given directly. The second line contains $$$n$$$ integers $$$a_i$$$ separated by space, the scale of every "testcases".
• $$$2.$$$ If $$$type = 1$$$, $$$a_i$$$ will be generated specially, the way of generating is written below. The second line contains six integers $$$x,y,z,b_1,b_2,m$$$. In the next $$$m$$$ line, the $$$i$$$-th line contains three integers $$$p_i,l_i,r_i$$$.

$$$type = 2$$$ only appear on testcases $$$23,24,25$$$. The way of generating is:

Guarantee that $$$n\ge 2$$$. If $$$n>2$$$ ,then $$$\forall\ 3\le i\le n,b_i=(x\times b_{i-1} +y \times b_{i-2} + z) \mod 2^{30}$$$

Guarantee that $$$1 \le p_i \le n ,p_m = n ,p_0 = 0$$$ and $$$\forall\ 0 \le i < m,p_i<p_{i+1}$$$.

For all $$$1 \le j \le m$$$ ,if index $$$i(1 \le i \le n)$$$ satisfies $$$p_{j-1} < i \le p_j$$$, then $$$a_i=(b_i\mod (r_j-l_j+1)) + l_j$$$.

The ways of generating is just to reduce the input time. Standard solution does not rely on it.

$$$\bf{Output}$$$

One integer, the answer.

$$$\bf{Constraints}$$$

The problem has $$$25$$$ testcases.

For testcases $$$1\sim 22,2 \le n \le 5 \times10^5,1\le a_i \le 10^6,type=0$$$.

For testcases $$$23\sim25,2 \le n \le 4\times 10^7,1 \le a_i \le 10^9 ,1\le m\le 10^5 ,1 \le l_i \le r_i\le 10^9,0 \le x,y,z,b_1,b_2 < 2^{30},type=1$$$

$$$\bf{D2T3\ The\ Centroid\ of\ a\ Tree\ 3s\ 256MB}$$$

Little Simple is learning discrete mathematics! It's about graph theory today! He makes two notes in class:

• $$$1.$$$ On a tree with $$$n$$$ vertices, there are $$$n-1$$$ undirected edges. There is exactly one simple path between two vertices. Delete a vertex and all edges that connect it, and the tree splits into several sub-trees; delete an edge(not delete vertex it connects, the same below), and the tree splits into exactly two sub-trees.
• $$$2.$$$ For a tree with $$$n$$$ vertices and a vertex $$$c$$$, we call vertex $$$c$$$ the centroid of the tree if after deleting vertex $$$c$$$ ,the vertex numbers of the left trees are all less than $$$\left\lfloor \frac{n}{2} \right\rfloor$$$($$$\left\lfloor x \right\rfloor$$$ here means floor function). For those tree whose vertices is more than one, the number of centroid is only $$$1$$$ or $$$2$$$.

After class, the teacher gives Little Simple a tree $$$S$$$ with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. It is Little Simple's homework to figure the sum of two splitting subtrees when cutting every edge, respectively, which is:

In the formula above, $$$E$$$ is the edge set of tree $$$S$$$, $$$(u ,v)$$$ is a edge that connects vertex $$$u$$$ and vertex $$$v$$$. $$$S'_u$$$ and $$$S'_v$$$ are two sub-tree into which tree $$$S$$$ is split after deleting edge $$$(u ,v)$$$.

Little Simple does not think his homework is simple, so he asks you for help.

$$$\bf{Input}$$$

Input contains several testcases

The first line contains a integer $$$T$$$, the number of testcases.

For every testcase:

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

The next $$$n-1$$$ lines contains all the edges on the tree.

$$$\bf{Output}$$$

For every testcase:

Output one integer, the answer.

$$$\bf{Constrains}$$$

$$$1 \le T \le 5,1 \le n \le 299995$$$