主页 讨论版 问题 名次 状态 统计

请自觉遵守比赛规则，违者严惩，不接受求情！
kr的树-j9国际集团直营

问题 E: kr的树

时间限制: 3000 ms  内存限制: 256 MB
提交: 37  解决: 14
[提交][状态][讨论版]

题目描述

kr有一棵n个节点的有根树,根节点为1,每个点都有一个权值

对于一个节点u,设其权值为w[u],如果存在父亲节点,设其父亲节点为fa[u]

kr非常喜欢这棵树,于是她给每个节点都定义了两个函数来描绘这个节点的美丽程度

对于一个节点u,有两个函数为F[u]  , G[u]

kr对他们的定义如下:

现在有两种操作:

0 u val        表示将w[u]改成val

1 u             表示查询F[u]和G[u]

Kr希望能有一个程序来快速解决这个问题,你能帮帮她吗?

输入

第一行为n,代表树的大小

第二行为n个正整数，第i个数代表第i个点初始时的权值w[i]。

接下来n-1行，每行两个整数u,v，代表u与v连有一条边。

接下来一行为一个正整数Q。

下面Q行，每一行格式为0 u val 或1 u。

输出

对于每种格式为1 u的询问，输出一行两个数，分别为F[u],G[u]

样例输入

3
1 2 3
1 2
2 3
1
1 3

样例输出

3 3

提示

单组数据

对于100%的数据

n<=200000

Q<=200000

点权的绝对值<10^9

[提交][状态][讨论版]