主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 E: kr的树

问题 E: kr的树

时间限制: 3 Sec  内存限制: 256 MB
提交: 23  解决: 4
[提交][状态][讨论版]

题目描述

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

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