首页 > 试题广场 >

小H和圣诞树

[编程题]小H和圣诞树
  • 热度指数：3 时间限制：C/C++ 5秒，其他语言10秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小H收到了一棵美丽的圣诞树，圣诞树是一棵树(废话)，有N个节点，编号为1~N，每个节点上都有一件礼物，礼物也分为N种，编号为1~N，每件礼物都有一个种类。
现在小H想问你Q个问题，每个问题形如x，y，表示询问所有满足下列条件的路径长度和：
路径的一个端点上的礼物种类是x，另一端点上礼物种类是y，且这条路径是简单路径
注意：
(x,y),(y,x)是相同的路径
树的每条边有边权，路径的长度为路径上所有边的长度和

输入描述:
第1行，一个整数N(1≤N≤100,000)
第2行N个属于[1,N]的正整数，依次表示每个节点上的礼物种类
接下来N-1行，每行三个正整数，依次表示树上的一条边的起点u、终点v、长度l (1≤u,v≤N,0≤l≤100,000)
接下来一行，一个整数Q(1≤Q≤100,000)
接下来Q行，每行两个整数x，y，意义见题目描述,1≤x,y≤N


输出描述:
对于每个询问输出一行，表示你给出的答案(答案保证在long long范围内)
示例1

输入

3
1 2 3
1 2 3
2 3 7
3
1 2
1 3
2 3

输出

3
10
7
算法知识视频讲解
添加回答

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

提交观点

问题信息

树
上传者：牛客301599号
难度：
0条回答 10浏览

热门推荐

通过挑战的用户

查看代码

相关试题

小H和圣诞树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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