#P7263. 我也许做了假题目

    ID: 7276 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2800省选/NOI-仙人掌图广度优先搜索圆方树LCA树上倍增树上差分深度优先搜索环形区间拆分差分标记区间修改事件排序扫描中维护贡献

我也许做了假题目

我也许做了假题目

题目描述

YMDragon 想做 NOIP 2016 的「天天爱跑步」,请 XLightGod 给他一份题目和数据,结果收到的是这个版本。

地图是一棵有 nn 个结点、mm 条边的仙人掌,即连通的无向图,每条边至多属于一个简单环。结点编号为 11 至 nn。保证所有环都包含奇数个结点,因此任意两个结点之间的最短路径唯一。

有 qq 名玩家,第 ii 名玩家的起点为 SiS_i,终点为 TiT_i。所有玩家在第 00 秒同时出发,以每秒经过一条边的速度沿各自的最短路径前进,中途不停,抵达终点后结束。

每个结点 jj 都有一名观察员,只在第 WjW_j 秒观察。若一名玩家恰好在该时刻到达结点 jj,他就会被观察到。玩家在出发时位于起点,在到达终点的那一刻也可以被观察到,但结束后不能继续被观察到。

求每个结点的观察员能观察到多少名玩家。

输入格式

第一行有三个整数 n,m,qn,m,q。其中,nn 表示仙人掌的结点数,同时也是观察员的数量;mm 表示图的边数;qq 表示玩家的数量。

接下来 mm 行,每行两个整数 u,vu,v,表示点 uu 和点 vv 之间有一条边。

接下来一行有 nn 个整数,其中第 jj 个整数为 WjW_j,表示结点 jj 的观察员观察的时刻。

接下来 qq 行,每行两个整数 Si,TiS_i,T_i,表示一个玩家的起点和终点。

输出格式

输出一行 nn 个整数,第 jj 个整数表示结点 jj 的观察员能观察到的玩家数量。

样例

样例 1

8 8 2
1 2
1 3
2 4
3 5
4 5
2 6
4 7
3 8
2 1 3 1 2 0 0 4
7 8
6 8
1 1 2 1 1 1 1 2

样例 2

见下发文件中的 problem2.in/ans。

样例 3

见下发文件中的 problem3.in/ans。

数据范围

测试点 限制
1–4 n,q≤5000n,q\le 5000
5–8 n,q≤100000n,q\le 100000,m=n−1m=n-1
9–12 n,q≤100000n,q\le 100000,m=nm=n
13–20 n,q≤100000n,q\le 100000

对于所有测试点,0≤Wj≤n0\le W_j\le n。

原 PDF 题面