http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1506. Missing On The Tree(张闻涛)
时间限制:1.5s   内存限制:256.0MB  
总提交次数:216   AC次数:57   平均分:37.43
将本题分享到:
   
 
问题描述
  你有一棵以1号节点为根的有根树。。。
输入格式
  第一行一个数n 表示节点个数
  第2到n行,每行一个数x,第i行的x表示i节点的父亲为x
  接下来一个数m,表示操作与询问个数的总和
  接下来m行,每行的开头有1个数p
  若p为0,则接下来有2个数x,y,表示将x号节点的权值加上y
  若p为1,则接下来有3个数x,y,z,表示将x号节点到y号节点的这条链上的每个节点的权值加上z
  若p为2,则接下来有2个数x,y,表示将以x号节点为根的子树的每个节点的权值加上z
  若p为3,则接下来有2个数x,y,表示询问x号节点到y号节点的这条链上每个节点的权值和,你需要输出这个和
  若p为4,则接下来有2个数x,y,表示询问x号节点到y号节点的这条链上每个节点的权值的最大值,你需要输出这个最大值
  若p为5,则接下来有2个数x,y,表示将x号节点的父亲改为y号节点
输出格式
  对于每个3与4操作,输出1行,表示答案
样例输入
3
1
1
2
1 2 3 -1
3 2 3
样例输出
-3
数据规模和约定
  保证任何时候每个节点的权值的绝对值小于40000
  4%的数据n,m<=5
  另外12%的数据n,m<=10000
  另外40%的数据,没有5操作
  另外20%的数据,没有2操作
  100%的数据 N<=50000,m<=100000