No.8106 Toptree is but what is not.
Problem Statement
First, you are given a tree with $N$ vertices. The vertices are numbered from $0$ to $N-1$. There are $N-1$ edges, and the $i$-th edge ( $0\leq i\leq N-2$ ) connects vertex $u_i$ and vertex $v_i$. For $2$ vertices $u$ , $v$ of the given tree, let $\text{dist}(u,v)$ denote the number of edges on the shortest path between $u$ and $v$. When $u=v$, $\text{dist}(u,v)=0$. Furthermore, you are given a sequence $(A_0,A_1,\ldots ,A_{N-1})$.
For integers $l$, $r$ satisfying $0\leq l\lt r\leq N$, a vertex $v$, a vertex $\delta$, and a non-negative integer $k$, define $f(l,r,v,\delta ,k)=10^{- {\!\!\!\! -100}}\text{dist}(v,\delta )+\sum_{w=l}^{r-1} (A_w+k)\text{dist}(v,w)$.
You are given $Q$ queries. In the $i$-th query $(0\leq i \leq Q-1)$, for the given non-negative integers $l_i$ , $r_i$ , ${\delta}_i$ , $k_i$, find the number of the vertex $v$ that minimizes the value of $f(l_i,r_i,v,{\delta}_i,k_i)$. Such a $v$ is unique under the constraints of this problem. Let $X_i$ be the answer to the $i$-th query.
Actually, in the $i$-th query, ${a^{\prime}}_i$ , ${b^{\prime}}_i$ , ${k^{\prime}}_i$ are given instead of $l_i$ , $r_i$ , $k_i$, so restore them by the following procedure using the answers to the previous queries.
- If $i=0$, let $a_i={a^{\prime}}_i$; if $i\neq 0$, let $a_i=\left( {a^{\prime}}_i+\sum_{j=0}^{i-1}X_j\right) \bmod N$.
- If $i=0$, let $b_i={b^{\prime}}_i$; if $i\neq 0$, let $b_i=\left( {b^{\prime}}_i+2\sum_{j=0}^{i-1}X_j\right) \bmod N$.
- If $i=0$, let $k_i={k^{\prime}}_i$; if $i\neq 0$, let $k_i=\left( {k^{\prime}}_i+\left(\sum_{j=0}^{i-1}X_j\right)^2\right)\bmod 150\ 001$.
- $l_i=\min\lbrace a_i, b_i \rbrace$
- $r_i=1+\max\lbrace a_i, b_i \rbrace$
Incidentally, $150\ 001$ is a prime number.
Constraints
The input satisfies the following constraints.
- $N = 150\ 000$
- $Q = 150\ 000$
- $0\leq u_i\leq N-1$
- $0\leq v_i\leq N-1$
- The graph formed by the given edges is a tree.
- $0\leq A_i\leq 150\ 000$
- $0\leq {a^{\prime}}_i\lt N$
- $0\leq {b^{\prime}}_i\lt N$
- $0\leq {k^{\prime}}_i\leq 150\ 000$
- $0\leq \delta_i\lt N$
- All input values are integers.
It is also guaranteed that the restored $l_i$ , $r_i$ , $k_i$ satisfy the following constraints.
- $0\leq l_i\lt r_i\leq N$
- $0\leq k_i\leq 150\ 000$
Input
The input is given in the following format.
$N$
$u_0$ $v_0$
$u_1$ $v_1$
$\vdots$
$u_{N-2}$ $v_{N-2}$
$A_0$ $A_1$ $\ldots$ $A_{N-1}$
$Q$
${a^{\prime}}_0$ ${b^{\prime}}_0$ ${k^{\prime}}_0$ $\delta_0$
${a^{\prime}}_1$ ${b^{\prime}}_1$ ${k^{\prime}}_1$ $\delta_1$
$\vdots$
${a^{\prime}}_{Q-1}$ ${b^{\prime}}_{Q-1}$ ${k^{\prime}}_{Q-1}$ $\delta_{Q-1}$
Output
$X_0$
$X_1$
$\vdots$
$X_{Q-1}$
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Nachia