问题2578--刀客塔的疑惑(arknights)

2578: 刀客塔的疑惑(arknights)

时间限制: 1 Sec  内存限制: 128 MB
提交: 13  解决: 9
[提交] [状态] [讨论版] [命题人:]

题目描述

刀客塔最近总是在寻思着为什么自己总是出不了六星,于是他去询问了ym大佬,ym大佬很仔细地告诉了他原因, 其实能抽出六星的概率和一棵包含N个结点的树(连通且无环)有关,这棵树第i号节点上包含一种颜色color[i](颜色种类不超过20),第i天, 官方会给定两个数u[i],v[i], 能抽出六星的概率就是1/(u[i]到v[i]的路径上的颜色种类),但是第i天x[i]到y[i]的路径的颜色会变成p[i],由于刀客塔已经丧失了理智,所以这个问题得留给你。

输入

第一行包含4个正整数N,M,R,分别表示树的结点个数、操作个数、根节点序号。
接下来一行包含N个非负整数,分别依次表示各个节点上初始的颜色。
接下来N−1行每行包含两个整数x,y,表示点x和点y之间连有一条边(保证无环且连通)
接下来M行每行包含若干个正整数,每行表示一组询问,格式如下:
包含个正整数x[i],y[i],p[i],u[i],v[i], 分别表示x[i]到y[i]的路径的颜色会变成p[i],u[i]与v[i]与题目相符合

输出

M行第i行一个整数x表示u[i]到v[i]的路径上的颜色种类。

样例输入 Copy

7 1 1
1 3 5 7 4 3 1
1 2
2 3
2 4
1 5
5 6
5 7
3 7 1 3 7

样例输出 Copy

1

提示

样例输入2:
7 2 1
1 3 5 7 4 3 1
1 2
2 3
2 4
1 5
5 6
5 7
3 7 1 4 6
2 2 2 3 4
样例输出2:
3
3
n≤1e5, m≤1e5, color[i]≤20

来源/分类