首页 > 试题广场 >

求子树

[编程题]求子树
  • 热度指数：1 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

给一个n个点的树，第i个点的值是vi，初始根是1。

有m个操作，每次操作：

1.将树根换为x。

2.给出两个点x，y，求所有点对(a,b)的个数满足a在x子树中，b在y子树中，va==vb


输入描述:
第一行两个数表示n，m
第二行n个数，表示每个点的点权vi
之后n-1行,每行两个数x,y表示一条边
之后m行，每行为：
1 x表示把根换成x点
2 x y表示查询x点的子树与y点的子树


输出描述:
对于每个询问，输出一行一个数表示答案
示例1

输入

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

输出

0
1
1
1

备注:
对于100%的数据，1 <= n <= 1e5 , 1<= m <= 5e5 , 1 <= vi <= 1e9
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

深度优先搜索(DFS)
上传者：牛客301599号
难度：
0条回答 14浏览

热门推荐

通过挑战的用户

查看代码

相关试题

求子树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号