2379. [HZOI 2015]QAQ的LIS树 II

【题目描述】

QAQ喜欢玩LIS，他觉得在树上的LIS非常的有趣

但是上一道题目已经耗尽了他所有的魔法值，所以他并不能人为对点权进行修改了

sad story。。

不过没有关系，QAQ是个非常爱玩的小孩子，他又提出了这样的一个问题：

QAQ有一棵树，节点总数为n，编号为0->n-1,树根为0

要求支持以下操作：

1、M u v 把u点的点权+v

2、S 查询最大的一棵子树，满足子树中所有的点到子树的根的路径都是一个上升序列

对于每次询问，QAQ想知道满足条件的子树最大是多少

【输入格式】

第一行输入n表示节点总数

之后有n-1个数，第i个数表示第i个节点的父亲

输入m表示操作总数

以下m行每行一个操作如题意所示

【输出格式】

对于每个询问输出对应的答案

【样例输入】

10



0 0 2 1 0 2 4 3 3



20



M 8 4



S



S



S



M 9 3



M 4 3



S



S



M 9 4



S



S



M 7 4



S



M 0 1



M 8 4



S



M 7 4



S



M 7 4



M 2 1 

【样例输出】

1



1



1



2



2



2



2



1



1



1

【提示】

有30%的数据，n<=1000,m<=2000

另外有20%的数据，树是随机的

另外有20%的数据，树是一条链

另外有10%的数据，所有非根节点的父亲都是根

对于100%的数据，n<=50000，m<=100000，v<=100000