简答题 偏难
#20186

树上旅行 时间限制:1 s,内存限制:512 MB 【问题描述】 给定一棵有 n 个结点的有根树,结点依次以 1、2、……、n 编号,其中根结点的编号为 1。…

树上旅行

时间限制:1 s,内存限制:512 MB

【问题描述】

给定一棵有 n 个结点的有根树,结点依次以 1、2、……、n 编号,其中根结点的编号为 1。

小 A 计划在这棵有根树上进行 q 次旅行。在第 i 次旅行中,小 A 首先会选定结点 si 作为起点,并移动若干次。移动分为以下两种:

(1)移动至当前结点的父结点。特殊地,如果当前位于根结点,则不进行移动。

(2)移动至当前结点的所有子结点中编号最小的结点。特殊地,如果当前位于叶子结点,则不进行移动。

由于移动次数可能很大,对于第 i 次旅行,旅行中的移动将以 ki 个不为零的整数构成的序列 ai,1、ai,2、……、ai,k 表示。

对于 ai,j,若 ai,j > 0 则代表进行 ai,j 次第一种移动;若 ai,j < 0 则代表进行 ai,j 次第二种移动。根据给出的序列从左至右完成所有移动后,小 A 所在的结点即是旅行的终点。

给定每次旅行的起点与移动序列,请你求出旅行终点的结点编号。

【输入描述】

第一行,两个正整数 n、q,分别表示有根树的结点数量,以及旅行次数。

第二行,n -1 个整数 p2、p3、……、pn,其中 pi 表示结点 i 的父结点编号。

接下来 2q 行中的第 2i - 1行(1<=i<=q )包含两个正整数 si、ki,分别表示第 i 次旅行的起点编号,以及移动序列的长度。

第 2i 行包含 k 个整数 ai,1、ai,2、……、ai,k,表示移动序列。

【输出描述】

输出共 q 行,第 i 行包含一个整数,表示第 i 次旅行终点的结点编号。

【样例输入1】

5 4
1 1 2 2
3 3
1 -1 -1
2 5
1 -1 1 -1 1
5 8
1 1 1 -1 -1 -1 -1 -1
5 3
-1 -1 1

【样例输出1】

4
1
4
2

【样例输入2】

8 3
5 4 2 1 3 6 6
8 1
8
8 2
8 -8
8 3
8 -8 8

【样例输出2】

1
7
1

【数据范围】

对于所有测试点,保证 1 <= n <= 10^5,1 <= q <= 2×10^4,1 <= pi、si <= n,ki >= 1,且Σki <= 10^5,1<=|ai,j|<=n。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; using namespace std; const int N = 1e5 + 5; const int L = 18; int n, q; int h[N], nx[N]; int par[L][N], son[L][N]; void dfs(int u) {     for (int i = 1; i &lt; L; i++)         par[i][u] = par[i - 1][par[i - 1][u]];     son[0][u] = u;     for (int i = h[u]; i; i = nx[i]) {         dfs(i);         if (son[0][u] == u || i &lt; son[0][u])             son[0][u] = i;     }     for (int i = 1; i &lt; L; i++)         son[i][u] = son[i - 1][son[i - 1][u]]; } int move(int go[L][N], int u, int step) {     for (int i = 0; i &lt; L; i++)         if ((step &gt;&gt; i) &amp; 1)             u = go[i][u];     return u; } int main() {     cin &gt;&gt; n &gt;&gt; q;     for (int i = 2; i &lt;= n; i++) {         cin &gt;&gt; par[0][i];         nx[i] = h[par[0][i]];         h[par[0][i]] = i;     }     par[0][1] = 1;     dfs(1);     while (q--) {         int s, k;         cin &gt;&gt; s &gt;&gt; k;         while (k--) {             int a;             cin &gt;&gt; a;             if (a &lt; 0)                 s = move(son, s, -a);             else                 s = move(par, s, a);         }         cout &lt;&lt; s &lt;&lt; endl;     }     return 0; }</pre>
这道题暂未补解析。