問題一覧 > 通常問題

No.2258 The Jikka Tree

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 3
作問者 : 👑 NachiaNachia
1 ProblemId : 8986 / 自分の提出
問題文最終更新日: 2023-03-31 22:28:03

問題文

まず、 NN 頂点の木が与えられます。頂点には 00 から N1N-1 まで番号が付けられています。 辺は N1N-1 個ありますが、 ii 番目の辺( 0iN20\leq i\leq N-2 )は頂点 uiu_i と頂点 viv_i を結びます。 与えられた木の 22 頂点 uu , vv に対して、 uu , vv 間の最短パスに含まれる辺の個数を dist(u,v)\text{dist}(u,v) と表します。 u=vu=v のときは dist(u,v)=0\text{dist}(u,v)=0 です。 さらに、数列 (A0,A1,,AN1)(A_0,A_1,\ldots ,A_{N-1}) が与えられます。

0l<rN0\leq l\lt r\leq N を満たす整数 ll, rr と頂点 vv 、頂点 δ\delta 、非負整数 kk に関して f(l,r,v,δ,k)=10100dist(v,δ)+w=lr1(Aw+k)dist(v,w)f(l,r,v,\delta ,k)=10^{-100}\text{dist}(v,\delta )+\sum_{w=l}^{r-1} (A_w+k)\text{dist}(v,w) と定義します。

ここで、 QQ 個のクエリが与えられます。 ii 番目のクエリ (0iQ1)(0\leq i \leq Q-1) では与えられる非負整数 lil_i , rir_i , δi{\delta}_i , kik_i に対して、 f(li,ri,v,δi,ki)f(l_i,r_i,v,{\delta}_i,k_i) の値を最小化するような vv の番号を求めてください。そのような vv はこの問題の制約のもとで一意です。 ii 番目のクエリの答えを XiX_i とします。

実際には、 ii 番目のクエリでは lil_i , rir_i , kik_i の代わりに ai{a^{\prime}}_i , bi{b^{\prime}}_i , ki{k^{\prime}}_i が与えられるので、それ以前のクエリの答えを用いて次の手順で復元してください。

  1. i=0i=0 のときは ai=aia_i={a^{\prime}}_ii0i\neq 0 のときは ai=(ai+j=0i1Xj)modNa_i=\left( {a^{\prime}}_i+\sum_{j=0}^{i-1}X_j\right) \bmod N とする。
  2. i=0i=0 のときは bi=bib_i={b^{\prime}}_ii0i\neq 0 のときは bi=(bi+2j=0i1Xj)modNb_i=\left( {b^{\prime}}_i+2\sum_{j=0}^{i-1}X_j\right) \bmod N とする。
  3. i=0i=0 のときは ki=kik_i={k^{\prime}}_ii0i\neq 0 のときは ki=(ki+(j=0i1Xj)2)mod150 001k_i=\left( {k^{\prime}}_i+\left(\sum_{j=0}^{i-1}X_j\right)^2\right)\bmod 150\ 001 とする。
  4. li=min{ai,bi}l_i=\min\lbrace a_i, b_i \rbrace
  5. ri=1+max{ai,bi}r_i=1+\max\lbrace a_i, b_i \rbrace

ちなみに、 150 001150\ 001 は素数です。

制約

入力は次の制約を満たします。

  • 1N150 0001\leq N \leq 150\ 000
  • 1Q150 0001\leq Q \leq 150\ 000
  • 0uiN10\leq u_i\leq N-1
  • 0viN10\leq v_i\leq N-1
  • 与えられた辺からなるグラフは木である
  • 0Ai150 0000\leq A_i\leq 150\ 000
  • 0ai<N0\leq {a^{\prime}}_i\lt N
  • 0bi<N0\leq {b^{\prime}}_i\lt N
  • 0ki150 0000\leq {k^{\prime}}_i\leq 150\ 000
  • 0δi<N0\leq \delta_i\lt N
  • 入力はすべて整数

また、復元された lil_i , rir_i , kik_i は次の制約を満たすことが保証されます。

  • 0li<riN0\leq l_i\lt r_i\leq N
  • 0ki150 0000\leq k_i\leq 150\ 000

入力

入力は次の形式で与えられます。

NN
u0u_0 v0v_0
u1u_1 v1v_1
\vdots
uN2u_{N-2} vN2v_{N-2}
A0A_0 A1A_1 \ldots AN1A_{N-1}
QQ
a0{a^{\prime}}_0 b0{b^{\prime}}_0 k0{k^{\prime}}_0 δ0\delta_0
a1{a^{\prime}}_1 b1{b^{\prime}}_1 k1{k^{\prime}}_1 δ1\delta_1
\vdots
aQ1{a^{\prime}}_{Q-1} bQ1{b^{\prime}}_{Q-1} kQ1{k^{\prime}}_{Q-1} δQ1\delta_{Q-1}

出力

X0X_0
X1X_1
\vdots
XQ1X_{Q-1}

サンプル

サンプル1
入力
5
0 1
1 3
3 2
3 4
1000 10 1 100 10000
15
0 0 0 0
0 1 150000 1
2 0 0 2
3 0 150000 3
4 2 150000 4
1 1 149975 0
0 0 149965 1
1 2 149951 2
1 4 149901 3
3 4 149804 4
2 0 149745 0
3 1 149639 1
1 4 149517 2
4 3 149375 3
0 1 149160 4
出力
0
0
0
1
4
1
1
3
4
2
3
3
3
4
4

クエリの内容を復元した ll , rr , kk で置き換えた入力データを次に示します。

5
0 1
1 3
3 2
3 4
1000 10 1 100 10000
15
0 1 0 0
0 2 150000 1
0 3 0 2
0 4 150000 3
0 5 0 4
1 2 150000 0
1 3 0 1
1 4 150000 2
1 5 0 3
2 3 150000 4
2 4 0 0
2 5 150000 1
3 4 0 2
3 5 150000 3
4 5 0 4

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。