bzoj#P3757. 苹果树
苹果树
题目描述
神犇家门口种了一棵苹果树。苹果树作为一棵树,当然是呈树状结构,每根树枝连接两个苹果,每个苹果都可以沿着一条由树枝构成的路径连到树根,而且这样的路径只存在一条。由于这棵苹果树是神犇种的,所以苹果都发生了变异,变成了各种各样的颜色。我们用一个 到 之间的正整数来表示一种颜色。树上一共有 个苹果。每个苹果都被编了号码,号码为一个 到 之间的正整数。我们用 代表树根。只会有一个苹果直接根。
有许许多多的人来神犇家里膜拜神犇。可神犇可不是随便就能膜拜的。前来膜拜神犇的人需要正确回答一个问题,才能进屋膜拜神犇。这个问题就是,从树上编号为 的苹果出发,由树枝走到编号为 的苹果,路径上经过的苹果一共有多少种不同的颜色(包括苹果 和苹果 的颜色)?不过神犇注意到,有些来膜拜的人患有色盲症。具体地说,一个人可能会认为颜色 就是颜色 ,那么他们在数苹果的颜色时,如果既出现了颜色 的苹果,又出现了颜色 的苹果,这个人只会算入颜色 ,而不会把颜色 算进来。
神犇是一个好人,他不会强人所难,也就会接受由于色盲症导致的答案错误(当然答案在色盲环境下也必须是正确的)。不过这样神犇也就要更改他原先数颜色的程序了。虽然这对于神犇来说是小菜一碟,但是他想考验一下你。你能替神犇完成这项任务吗?
输入格式
输入第一行为两个整数 和 ,分别代表树上苹果的个数和前来膜拜的人数。
接下来的一行包含 个数,第 个数代表编号为 的苹果的颜色 。
接下来有 行,每行包含两个数 和 ,代表有一根树枝连接了苹果 和 (或者根和一个苹果)。
接下来有m行,每行包含四个整数 ,代表这个人要数苹果 到苹果 的颜色种数,同时这个人认为颜色 就是颜色 。如果 ,则代表这个人没有患色盲症。
输出格式
输出一共 行,每行仅包含一个整数,代表这个人应该数出的颜色种数。
5 3
1 1 3 3 2
0 1
1 2
1 3
2 4
3 5
1 4 0 0
1 4 1 3
1 4 1 2
2
1
2
数据规模与约定
对于 的数据,,,,。
此题存在版权,故原 BZOJ 不再支持提交,保留在此只供大家参考题面! 望见谅!