Iscat-am frumuseţi şi preţuri noi.
Biciul răbdat se-ntoarce în cuvinte
Si izbăveste-ncet pedesitor
Odrasla vie-a crimei tuturor.
You are given a tree with $$$N$$$ nodes and $$$N-1$$$ undirected edges. You will to find the lexicographically minimal bamboo coloring of the given tree. A bamboo coloring of a tree satisfies all of the following constraints:
- Each node $$$u \in [1,N]$$$ is colored with a color $$$c_u \in [1,N]$$$;
- Each node $$$u \in [1,N]$$$ is adjancent to at most $$$2$$$ other nodes with the same color as $$$u$$$;
- For each color $$$c \in [1,N]$$$, all nodes colored with color $$$c$$$ form a connected component of the tree.
The first line of input contains one integer $$$N$$$ ($$$1 \le N \le 10^5$$$) — the number of nodes in the tree.
Each of the next $$$N-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le N$$$), meaning that there exists an undirected edge between nodes $$$u$$$ and $$$v$$$.
It is guaranteed that the graph given in the input forms a tree.
Print $$$N$$$ integers $$$c_1,c_2,\ldots, c_n$$$ ($$$1 \le c_i \le N$$$) coresponding to the lexicographically minimal bamboo coloring of the given tree, where $$$c_u$$$ ($$$u \in [1,N]$$$) represents the color of node $$$u$$$.
| Group | Additional constraints | Points |
| $$$1$$$ | $$$N \le 7$$$ | $$$10$$$ |
| $$$2$$$ | $$$N \le 5 \cdot 10^3$$$ | $$$40$$$ |
| $$$3$$$ | $$$N \le 10^5$$$ | $$$50$$$ |
8 1 2 1 3 1 4 1 5 4 7 4 8 5 6
1 1 1 2 3 3 2 2
9 1 9 9 2 9 7 7 6 7 8 7 4 6 3 6 5
1 1 2 2 3 2 2 4 1
The tree from the first sample
In this image, color $$$1$$$ is represented by green, color $$$2$$$ by blue, and color $$$3$$$ by yellow.
A fost ca niciodată.
Din rude mari împărăteşti,
O prea frumoasă fată.
Şi era una la părinţi
Şi mândră-n toate cele,
Cum e Fecioara între sfinţi
Şi luna între stele.
After solving "Traveling salesman" problem in $$$O(E+V)$$$, multiplying polynomials in $$$O(N)$$$, proving the Collatz conjecture, understanding physics and finding a quadratic algorithm for multiplying matricies, $$$K0Kalaru47$$$ challanges you with this problem, in exchange for a chance of winning this $$$InfOleague™$$$ contest.
You are given an array $$$A$$$ of $$$N$$$ values smaller than $$$M$$$. The cost of a subset is the minimum $$$xor$$$ across all pairs in the subset. More formally, the cost of a set $$$B= {B_1,B_2,...,B_k}$$$ is equal to $$$min_{i \neq j \in [1,k]} (B_i \oplus B_j)$$$, where $$$\oplus$$$ denotes the bitwise xor operation. Find the sum of costs across all possible subsets of length greater than $$$1$$$ modulo $$$MOD$$$.
The input consists of integers $$$N,M,MOD$$$ followed by an array $$$A$$$ of length $$$N$$$ with values in range $$$[0,M]$$$.
Print one integer: The sum of costs across all subsets of length greater than $$$1$$$.
- For all test data , $$$N \cdot M \le 10^6$$$ , $$$2 \le MOD \le 10^9$$$
- For 30 points , $$$N,M \le 100$$$
- For the remaining $$$70$$$ points, there are no further restrictions
- Note that $$$MOD$$$ may not be a prime number !
3 5 666013 4 2 5
15
12 100 66013 32 69 39 51 49 30 51 32 0 0 0 100
16807
In the first sample , all the possible subsets are :
- $$$[1,2,3]$$$ with cost $$$min(a[1] \oplus a[3],a[2] \oplus a[3],a[1] \oplus a[3])$$$ = 1
- $$$[1,2]$$$ with cost $$$min(a[1] \oplus a[2]) = 6$$$
- $$$[2,3]$$$ with cost $$$min(a[1] \oplus a[3]) = 1$$$
- $$$[1,3]$$$ with cost $$$min(a[2] \oplus a[3]) = 7$$$
Therefore, the final answer is $$$1+6+1+7 = 15$$$
In a very large $$$2 \cdot 10^9 \times 2 \cdot 10^9$$$ grid, there are initially $$$N$$$ active points with known coordinates.
You are also given $$$Q$$$ queries, which you will have to process in order. Each query can be of either one of the following two types:
- ! x y — Toggle the state of the point at coordinates $$$(x,y)$$$. If the point at $$$(x,y)$$$ used to be active, it will now be inactive, and vice-versa.
- ? x1 y1 x2 y2 — Print the number of ways to get from an active point at coordinates $$$(x_1,y_1)$$$ to another active point at coordinates $$$(x_2,y_2)$$$ by only jumping through active points. It is possible to jump from an active point $$$(a,b)$$$ to another active point $$$(c,d)$$$ if and only if $$$a \lt c$$$. Since the number of ways to get from $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$ can be very large, print its remainder modulo $$$10^9+7$$$.
The first line of input contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N, Q \le 3 \cdot 10^5$$$) — the number of initial active points, and the number of queries, respectively.
The second line of input contains $$$N$$$ integers $$$x_1,x_2,\ldots,x_n$$$ ($$$-10^9 \le x_i \le 10^9$$$), the $$$x$$$-coordinates of the initially active points.
The third line of input contains $$$N$$$ integers $$$y_1,y_2,\ldots,y_n$$$ ($$$-10^9 \le y_i \le 10^9$$$), the $$$y$$$-coordinates of the initially active points.
It is guaranteed that all $$$N$$$ points are pairwise distinct.
The next $$$Q$$$ lines contain the descriptions of the queries, one line per query:
Each query can have one of the following two formats:
- ! x y. In this case, it is guaranteed that $$$-10^9 \le x,y \le 10^9$$$;
- ? x1 y1 x2 y2. In this case, it is guaranteed that $$$-10^9 \le x_1,y_1,x_2,y_2 \le 10^9$$$ and that both $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ are active points.
For every second type query, print one integer, the number of ways to get from $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$ by only jumping through active points. Since this number can be very large, print its remainder modulo $$$10^9+7$$$.
| Group | Additional constraints | Points |
| $$$1$$$ | $$$Q,N \le 200$$$ | $$$10$$$ |
| $$$2$$$ | $$$Q,N \le 2000$$$ | $$$15$$$ |
| $$$3$$$ | The absolute value of all coordinates does not exceed $$$10^5$$$. | $$$25$$$ |
| $$$4$$$ | $$$Q,N \le 10^5$$$ | $$$20$$$ |
| $$$5$$$ | $$$Q,N \le 3 \cdot 10^5$$$ | $$$30$$$ |
7 7 -1 -2 2 -1 0 3 -3 -2 -1 0 1 3 3 4 ? -1 -2 3 3 ? 2 0 2 0 ? 3 3 -1 -2 ! 2 2 ? -2 -1 0 3 ! -2 -1 ? -3 4 3 3
4 1 0 3 18
The $$$7$$$ initial active points For the first query, the $$$4$$$ paths from $$$(-1,-2)$$$ to $$$(3,3)$$$ are:
- $$$(-1,-2) \to (3,3)$$$;
- $$$(-1,-2) \to (0,3) \to (3,3)$$$;
- $$$(-1,-2) \to (2,0) \to (3,3)$$$;
- $$$(-1,-2) \to (0,3) \to (2,0) \to (3,3)$$$
For the second query, it is possible to get from $$$(2,0)$$$ to $$$(2,0)$$$ only by not jumping at all.
For the third query, it is impossible to get from $$$(3,3)$$$ to $$$(-1,2)$$$.
The fourth query toggles the state of point $$$(2,2)$$$, making it active. Similarly, the $$$6$$$-th query deactivates point $$$(-2,-1)$$$.