[Ynoi2000] tmostnrq2

Luogu
IDLGP9999
Time12000ms
Memory512MB
DifficultyP7
2000O2优化Ynoi
给定 $n$ 个顶点的树,顶点编号为 $1,\dots,n$,给定长度 $n_0$ 的序列 $a_1,\dots,a_{n_0}$,共 $m$ 次查询,每次查询给定 $l,r,x$,问树的顶点 $x$,依次向 $a_l,\dots,a_r$ 移动一步,到达的顶点。 若 $x=y$,则从顶点 $x$ 向 $y$ 移动一步到达 $x$,否则到达与 $x$ 在树上相邻且距离 $y$ 最近的位置。 ## Input 第一行三个整数 $n,n_0,m$; 接下来一行 $n-1$ 个整数依次表示 $f_2,\dots,f_n$,其中 $f_i$ 是顶点 $i$ 的父亲,$1$ 为根; 接下来一行 $n_0$ 个整数,依次表示 $a_1,\dots,a_{n_0}$; 接下来 $m$ 行,每行三个整数 $l,r,x$ 表示一次查询。 ## Output 共 $m$ 行,依次为每次查询的答案。 [samples] ## Note Idea:Ynoi,Solution:zhoukangyang&ccz181078,Code:zhoukangyang,Data:ccz181078 对于 $100\%$ 的数据,满足 $1\le n,n_0,m\le 10^6$;
Samples
Input #1
5 4 3
1 1 3 3
5 2 2 3
3 4 5
1 3 4
1 2 1
Output #1
3
2
1
API Response (JSON)
{
  "problem": {
    "name": "[Ynoi2000] tmostnrq2",
    "description": {
      "content": "给定 $n$ 个顶点的树,顶点编号为 $1,\\dots,n$,给定长度 $n_0$ 的序列 $a_1,\\dots,a_{n_0}$,共 $m$ 次查询,每次查询给定 $l,r,x$,问树的顶点 $x$,依次向 $a_l,\\dots,a_r$ 移动一步,到达的顶点。 若 $x=y$,则从顶点 $x$ 向 $y$ 移动一步到达 $x$,否则到达与 $x$ 在树上相邻且距离 $y$ 最近的位置。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 12000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9999"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $n$ 个顶点的树,顶点编号为 $1,\\dots,n$,给定长度 $n_0$ 的序列 $a_1,\\dots,a_{n_0}$,共 $m$ 次查询,每次查询给定 $l,r,x$,问树的顶点 $x$,依次向 $a_l,\\dots,a_r$ 移动一步,到达的顶点。\n\n若 $x=y$,则从顶点 $x$ 向 $y$ 移动一步到达 $x$,否则到达与 $x$ 在树上相邻且距离 $y$ 最近的位置。\n\n#...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments