#P3365. [Usaco2004 Feb]Distance Statistics 路程统计

    ID: 2554 传统题 1000ms 512MiB 尝试: 460 已通过: 214 难度: 6 上传者: 标签>CF2000提高+/省选-点分治树重心相向双指针点分治容斥去重Orange

[Usaco2004 Feb]Distance Statistics 路程统计

题目描述

有 NN 个农场,编号为 11 到 NN。它们由 MM 条双向道路连接,任意两个农场之间恰有一条简单路径。两农场的距离是这条路径上各条道路长度之和。

2≤N≤400002\le N\le40000,M=N−1M=N-1。每条道路的长度是 11 到 10001000 的整数。

给定整数 KK,求有多少对不同的农场距离不超过 KK。同一对农场只计一次。

输入格式

第一行两个整数 N,MN,M。

接下来 MM 行,每行两个农场编号 u,vu,v、一个道路长度 LL 和一个字符 DD。字符 N、E、S、W 表示从 uu 到 vv 的方位。每条道路均可双向通行。

最后一行给出一个整数 KK,满足 1≤K≤1091\le K\le10^9。

输出格式

输出一个整数,表示满足要求的无序农场对数。

样例

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
10
5

同场地图定义(Navigation Nightmare)

题目来源