{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003cfont color\u003d\"#000\"\u003eProblem F:\u003c/font\u003e \u003c/h1\u003e\n\n\u003cp\u003e\nYou 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:\n\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. Note that a node is an ancestor of itself.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e\nYour job is to write a program that performs a sequence of these operations on a given tree and calculates\nthe value that each Q operation will print. To avoid too large output file, your program is requested to\nprint the sum of the outputs of all query operations. Note that the judges confirmed that it is possible to\ncalculate every output of query operations in a given sequence.\n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cp\u003e\nThe input consists of multiple datasets. Each dataset has the following format:\n\u003c/p\u003e\n\n\u003cp\u003e\nThe 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\n\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.\n\u003c/p\u003e\n\u003cp\u003e\nThe 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.\n\u003c/p\u003e\n\u003cp\u003e\nThe 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.\n\u003c/p\u003e\n\n\u003cp\u003e\nThe last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed.\n\u003c/p\u003e\n\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\nFor each dataset, print the sum of the outputs of all query operations in one line.\n\u003c/p\u003e\n\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\n\u003ch2\u003eOutput for the Sample Input\u003c/h2\u003e\n\u003cpre\u003e4\n\u003c/pre\u003e\n\n\n"}}]}