TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4094
  • 题目
  • P4094[HAOI2016]地图
    限制 : 时间限制 : 20000 MS   空间限制 : 265536 KB
    评测说明 : 1s,256m
    问题描述

    一天rin来到了一个遥远的都市。这个都市有n个建筑,编号从1到n,其中市中心编号为1,这个都市有m条双向通行的街道,每条街道连接着两个建筑,其中某些街道首尾相连连接成了一个环。rin通过长时间的走访,已经清楚了这个都市的两个特点:
    1. 从市中心出发可以到达所有的建筑物。
    2. 任意一条街道最多存在与一个简单环中。令

    rin心花怒放的是,每个建筑物都会有拉面售卖。拉面有很多不同的种类,但对于rin而言只有油腻程度的不同,因此我们把油腻程度相同的拉面看做同一种拉面。由于不同建筑物的拉面的油腻程度可能不同,我们用一个正整数来表示拉面的油腻程度。要知道,拉面可是rin的最爱,但是现在到了下班高峰期,都市的交通变得非常的堵塞。 rin只能通过没有被堵死的街道通行,去品尝所在建筑物的拉面。

    现在rin想知道,如果她正在编号为x的建筑物,那么在从市中心到x的所有简单路径经过的街道都被堵死的情况下,rin可以品尝到的拉面中(注意没有出现的拉面是不能算在里面的):

    1. 油腻程度≤ y且品尝次数为奇数次的拉面有多少种?

    2. 油腻程度≤ y且品尝次数为偶数次的拉面有多少种?

    输入格式

    第一行两个正整数n,m,含义如题所示第二行一共N个正整数,第i个数Ai表示第i个建筑物出售的拉面的油腻程度。

    接下来M行,每行两个正整数x,y,表示在建筑物x,y之间有一条双向通行的街道。数据保证1<=x<y<=N

    接下来一行一个正整数Q,表示询问个数。

    接下来Q行每行三个非负整数ty,x,y,x表示询问的建筑物编号,y表示油腻程度的限制,ty=0时表示询问偶数,ty=1表示询问奇数。

    N<=100000,M<=150000,Q<=100000,Ai<=10^6

    提示:请注意数据范围中的<=,特殊条件中提到的y均为询问中的y,对于所有的数据,有y<=10^6

    输出格式

    一共Q行,对于每个询问输出一个答案。