Skip to content

14249: 【原4249】节点深度

题目

题目描述

author: fur 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4249

节点深度

题目描述

有一棵有根有边权的树,每次询问某个节点到根的距离
为了简便起见,每个节点的父节点的序号都比它小,节点的序号是\(0 base\)的
或许某个时刻助教忽然觉得这道题太简单了,决定更改树的根

输入格式

第一行两个数\(n, m\),表示节点个数与操作数
接下来\(n - 1\)行,每行两个数,表示从第\(1\)个节点到第\(n - 1\)个节点,每个节点的父节点序号\(f\)和到父节点的距离\(l\)
接下来\(m\)行,每行两个数\(opt, x\),当\(opt = 0\)时为询问节点\(x\)到根的距离,当\(opt = 1\)时将根调整为节点\(x\)

输出格式

对于每个\(opt = 0\)输出一个数表示距离

样例输入1

4 5
0 1
1 1
2 1
0 2
1 3
0 2
1 1
0 0

样例输出1

2
1
1

数据规模

对于100%的数据有
\(0 \leq f_i < i\)
\(0 \leq x < n\)
\(0 \leq \sum l_i < range(int)\)
对于20%的数据有
\(\sum opt_i = 0\)
对于另外20%的数据有
\(1 \leq m \leq 100\)
对于另外20%的数据有
\(f_i = random() \% i\)
对于另外20%的数据有
\(\sum opt_i \leq 100\)
对于100%的数据有
\(n \leq 100000\)
\(m \leq 100000\)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!