TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7847
  • 题目
  • P7847查询祖先
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 256MB
    问题描述

    给你一颗含有 \(n\) 个节点的树,最开始只有 $1$ 点被标记,即 $1$ 是根节点,现在有 \(Q\) 次操作,每一次操作类型如下:

    \(M \ x\) :代表将编号为 \(x\) 的节点标记。

    \(Q \ x\) :代表查询距离 \(x\) 节点最近的被标记的祖先节点的编号。

    现在想让你求所有查询到的节点编号总和为多少?

    输入格式

    第一行输入一个整数 \(T\),代表有 \(T\) 组测试数据。

    对于每一组测试数据,第一行输入两个数 \(n\)\(q\),代表节点的数量以及查询的次数

    第二行输入 \(n - 1\) 个数,其中 \(a[i]\) 表示编号 \(i + 1\) 的父亲节点是 \(a[i]\)

    接下来 \(q\) 行,每一行输入一个操作,操作格式和题目描述一致。

    \(1\le T\le 10\)

    \(1\le n,q\le 10^5\)

    保证数据能够构成一颗树。

    输出格式

    对于每一组数据,输出一行,代表所有查询到的节点编号总和

    样例输入

    1
    6 3
    1 1 2 3 3
    Q 5
    M 3
    Q 5

    样例输出

    4

    提示

    第一次查询:只有根节点标记,故5的最近标记的节点为1,第二次查询5的时候,5的父亲节点是3,且已被标记,所以此次编号为3,故答案为1+3=4.