Hello codeforces!↵
↵
CSP-J/S(Certified Software Professional-Junior/Senior) of China ended. CSP-J/S (or you can say NOIp ,but it has been dead) was held by OI rules. In OI rules, every problem has the same score distribution $100$ points. In one problem, there is several testdatas (like $10$ ,$20$ or $25$). Every testdata has the same score distributions. Once you pass a testdata, you can get the score. You can submit your code during the contest, but can't see the result. The organizer will judge all the programs together after contest.↵
↵
I'd like to share the problems of CSP-S here! Hope you guys enjoy. Don't mind my poor English, I spent a whole afternoon translating.↵
↵
<spoiler summary="D1T1 code">↵
$\bf{D1T1\ Grey\ Code\ 1s\ 256MB}$↵
↵
$\bf{Statement}$↵
↵
_Grey 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 _Grey Code_ is $00,01,11,10$.↵
↵
We give an algorithm of generating _Grey Code_ below:↵
↵
- $1.$ $1$-bit _Grey Code_ consist of two $1$-bit binary string: $0,1$↵
↵
- $2.$ The first $2^n$ binary strings of $(n+1)$-bit _Grey Code_ is $n$-bit _Grey 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 _Grey Code_ is $n$-bit _Grey Code_($2^n$ binary strings in total) generated by this algorithm **being reversed** ,then adding a prefix $1$.↵
↵
We number all the _Grey Code_ from $0$ to $2^n-1$. Now you task is to figure out the $k$-th binary string of $n$-bit _Grey Code_.↵
↵
$\bf{Input}$↵
↵
Only two integer $n ,k$ ,the bit of _Grey 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$↵
</spoiler>↵
↵
<spoiler summary="D1T2 brackets">↵
↵
↵
$\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$↵
</spoiler>↵
↵
<spoiler summary="D1T3 tree">↵
↵
↵
$\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 disappear.↵
↵
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 $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$↵
↵
↵
</spoiler>↵
↵
<spoiler summary="D2T1 meal">↵
↵
↵
$\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 them 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 meal is 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$↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="D2T2 partition">↵
↵
↵
$\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:↵
$$↵
\sum\limits^{k_1}_{i=1}a_i \le \sum\limits^{k_2}_{i=k_1+1}a_i \le ... \le \sum\limits^{n}_{i=k_{p}+1}a_i↵
$$↵
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**:↵
$$↵
(\sum\limits^{k_1}_{i=1}a_i)^2 + (\sum\limits^{k_2}_{i=k_1+1}a_i)^2+...+(\sum\limits^{n}_{i=k_{p}+1}a_i)^2↵
$$↵
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$↵
</spoiler>↵
↵
<spoiler summary="D2T3 centroid">↵
↵
↵
$\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:↵
$$↵
\sum\limits_{(u,v)\in E} \left( \sum\limits_{ \qquad\ {1\le x \le n}\\ x\text{ is the centroid of } S'_u }x + \sum\limits_{ \qquad\ {1\le y \le n}\\ x\text{ is the centroid of } S'_v }y \right)↵
$$↵
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$↵
</spoiler>↵
↵
↵
CSP-J/S(Certified Software Professional-Junior/Senior) of China ended. CSP-J/S (or you can say NOIp ,but it has been dead) was held by OI rules. In OI rules, every problem has the same score distribution $100$ points. In one problem, there is several testdatas (like $10$ ,$20$ or $25$). Every testdata has the same score distributions. Once you pass a testdata, you can get the score. You can submit your code during the contest, but can't see the result. The organizer will judge all the programs together after contest.↵
↵
I'd like to share the problems of CSP-S here! Hope you guys enjoy. Don't mind my poor English, I spent a whole afternoon translating.↵
↵
<spoiler summary="D1T1 code">↵
$\bf{D1T1\ Grey\ Code\ 1s\ 256MB}$↵
↵
$\bf{Statement}$↵
↵
_Grey 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 _Grey Code_ is $00,01,11,10$.↵
↵
We give an algorithm of generating _Grey Code_ below:↵
↵
- $1.$ $1$-bit _Grey Code_ consist of two $1$-bit binary string: $0,1$↵
↵
- $2.$ The first $2^n$ binary strings of $(n+1)$-bit _Grey Code_ is $n$-bit _Grey 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 _Grey Code_ is $n$-bit _Grey Code_($2^n$ binary strings in total) generated by this algorithm **being reversed** ,then adding a prefix $1$.↵
↵
We number all the _Grey Code_ from $0$ to $2^n-1$. Now you task is to figure out the $k$-th binary string of $n$-bit _Grey Code_.↵
↵
$\bf{Input}$↵
↵
Only two integer $n ,k$ ,the bit of _Grey 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$↵
</spoiler>↵
↵
<spoiler summary="D1T2 brackets">↵
↵
↵
$\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$↵
</spoiler>↵
↵
<spoiler summary="D1T3 tree">↵
↵
↵
$\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 disappear.↵
↵
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 $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$↵
↵
↵
</spoiler>↵
↵
<spoiler summary="D2T1 meal">↵
↵
↵
$\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 them 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 meal is 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$↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="D2T2 partition">↵
↵
↵
$\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:↵
$$↵
\sum\limits^{k_1}_{i=1}a_i \le \sum\limits^{k_2}_{i=k_1+1}a_i \le ... \le \sum\limits^{n}_{i=k_{p}+1}a_i↵
$$↵
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**:↵
$$↵
(\sum\limits^{k_1}_{i=1}a_i)^2 + (\sum\limits^{k_2}_{i=k_1+1}a_i)^2+...+(\sum\limits^{n}_{i=k_{p}+1}a_i)^2↵
$$↵
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$↵
</spoiler>↵
↵
<spoiler summary="D2T3 centroid">↵
↵
↵
$\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:↵
$$↵
\sum\limits_{(u,v)\in E} \left( \sum\limits_{ \qquad\ {1\le x \le n}\\ x\text{ is the centroid of } S'_u }x + \sum\limits_{ \qquad\ {1\le y \le n}\\ x\text{ is the centroid of } S'_v }y \right)↵
$$↵
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$↵
</spoiler>↵
↵
