问题 1226. -- kr的树

1226: 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

来源

-rw-rw-rw-

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