{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027],[\u0027\\[\u0027,\u0027\\]\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003ch1\u003e\u003cfont color\u003d\"#000\"\u003eProblem F:\u003c/font\u003e \u003c/h1\u003e \n \u003cp\u003e You are given a tree \u003ci\u003eT\u003c/i\u003e that consists of \u003ci\u003eN\u003c/i\u003e nodes. Each node is numbered from 1 to \u003ci\u003eN\u003c/i\u003e, and node 1 is always the root node of \u003ci\u003eT\u003c/i\u003e. Consider the following two operations on \u003ci\u003eT\u003c/i\u003e: \u003c/p\u003e \n \u003cul\u003e \n \u003cli\u003e\u003cspan\u003eM v\u003c/span\u003e: (Mark) Mark node \u003cspan\u003ev\u003c/span\u003e.\u003c/li\u003e \n \u003cli\u003e\u003cspan\u003eQ v\u003c/span\u003e: (Query) Print the index of the nearest marked ancestor of node \u003cspan\u003ev\u003c/span\u003e which is nearest to it. Initially, only the root node is marked.\u003c/li\u003e \n \u003c/ul\u003e \n \u003cp\u003e Your job is to write a program that performs a sequence of these operations on a given tree and calculates the value that each Q operation will print. To avoid too large output file, your program is requested to print the sum of the outputs of all query operations. Note that the judges confirmed that it is possible to calculate every output of query operations in a given sequence. \u003c/p\u003e \n \u003ch2\u003eInput\u003c/h2\u003e \n \u003cp\u003e The input consists of multiple datasets. Each dataset has the following format: \u003c/p\u003e \n \u003cp\u003e The first line of the input contains two integers \u003ci\u003eN\u003c/i\u003e and \u003ci\u003eQ\u003c/i\u003e, which denotes the number of nodes in the tree \u003ci\u003eT\u003c/i\u003e and the number of operations, respectively. These numbers meet the following conditions: 1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 100000 and 1 ≤ \u003ci\u003eQ\u003c/i\u003e ≤ 100000. \u003c/p\u003e \n \u003cp\u003e The following \u003ci\u003eN\u003c/i\u003e - 1 lines describe the configuration of the tree \u003ci\u003eT\u003c/i\u003e. Each line contains a single integer \u003ci\u003ep\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e (\u003ci\u003ei\u003c/i\u003e \u003d 2, ... , \u003ci\u003eN\u003c/i\u003e), which represents the index of the parent of \u003ci\u003ei\u003c/i\u003e-th node. \u003c/p\u003e \n \u003cp\u003e The next \u003ci\u003eQ\u003c/i\u003e lines contain operations in order. Each operation is formatted as \"\u003cspan\u003eM v\u003c/span\u003e\" or \"\u003cspan\u003eQ v\u003c/span\u003e\", where \u003ci\u003ev\u003c/i\u003e is the index of a node. \u003c/p\u003e \n \u003cp\u003e The last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed. \u003c/p\u003e \n \u003ch2\u003eOutput\u003c/h2\u003e \n \u003cp\u003e For each dataset, print the sum of the outputs of all query operations in one line. \u003c/p\u003e \n \u003ch2\u003eSample Input\u003c/h2\u003e \n \u003cpre\u003e6 3\n1\n1\n2\n3\n3\nQ 5\nM 3\nQ 5\n0 0\n\u003c/pre\u003e \n \u003ch2\u003eOutput for the Sample Input\u003c/h2\u003e \n \u003cpre\u003e4\n\u003c/pre\u003e \n \u003c/body\u003e\n\u003c/html\u003e\n\u003cbr\u003e给出一颗树,有两种操作:\n\u003cbr\u003e1.M u 标记结点u\n\u003cbr\u003e2.Q u 询问离u最近的且被标记的祖先结点是哪个\n\u003ch3\u003e输入\u003c/h3\u003e\n\u003cbr\u003e有多组数据,每组第一行包含两个整数n和q表示树中的节点数和操作数\n\u003cbr\u003e接下来n-1行是树每行一个整数fa[i]表示i的父亲节点是fa[i](i\u003d2,……n)\n\u003cbr\u003eq行为M v或者 Q v,v是节点\n\u003cbr\u003e最后一组数据为0 0\n\u003ch3\u003e输出\u003c/h3\u003e\n每组数据在输出所有查询操作之和(1≤N≤100000和1≤q≤100000)\n\n\n"}}]}