问题 C: 【最近公共祖先3】 树结构不变的情况下，树上点的统计和修改《[Noi2015]软件包管理器》

---

【题目描述】

【题目描述】 就是给出一个n个点(0~n-1) 的有根树（根为0），和q次操作；初始时树上所有结点权值均为0； 1、操作将根到x结点的所有结点权值置为1，并输出这次操作有多少个元素的改变了状态； 2、操作将x结点的子树中所有结点权值置为0，并输出这次操作有多少个元素的改变了状态； （n，q<=100000） 【输入格式】 输入文件的第1行包含1个正整数n。随后一行包含n−1个整数，相邻整数之间用单个空格隔开，分别表示1,2,3,…,n−2,n−1点的父亲节点。 接下来一行包含1个正整数q，表示询问的总数。之后q行，每行1个询问。询问分为两种： Install x：表示1操作 Uninstall x：表示2操作 对于每个操作，输出这步操作有多少个点改变了状态。 【输出格式】 输出文件包括q行。 输出文件的第i行输出1个整数，为第i步操作中改变状态的点数。 Sample Input 7 0 0 0 1 1 5 5 install 5 install 6 uninstall 1 install 4 uninstall 0   Sample Output 3 1 3 2 3

题目类型~

 

咻咻~

提交答案 状态 返回作业