2377. [HZOI 2015]QAQ的LIS树

【题目描述】

QAQ喜欢玩LIS，有一天他看到这样的一道题目：

给定一棵树，求最长的路径使得路径上所有的点权连起来是一个上升序列

他思考了一下用树分治切掉了这道题目，不过QAQ觉得这样的题目非常的因缺思烃

于是就有了如下题目：

QAQ生成了一棵树，树的大小为n，节点为0->n-1，根为0

一开始所有点权都是0，有如下操作：

1、M u v QAQ施展LIS大魔法，将u点的点权+v

2、C u  QAQ施展LIS小魔法，他可以花费1点魔法值将某个点的点权+1，他现在希望u点到根节点的路径所有的点权构成一个上升序列

他需要你告诉他最少需要花费多少点魔法值才能完成这件事情

注意由于QAQ很懒而且很弱，魔法值很少，所以对于操作2他并不会去真正的更改点权，也就是2的询问对点权不会产生影响

【输入格式】

第一行输入n表示点数

以下n-1行，每行一个正整数，第i行的正整数表示i节点的父亲

之后输入m表示操作次数

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

【输出格式】

对于每个操作2输出答案

【样例输入】

5



0



1



1



2



5



M 4 1572



M 4 13890



C 1



C 4



C 0

【样例输出】

1



46392



0

【提示】

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

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

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

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

对于100%的数据，n<=50000,m<=100000,v<=2^16

出题人非常的良心，开了标程两倍左右的时限OwO