#P4046. [Cerc2014]Pork barrel

    ID: 3248 传统题 4000ms 128MiB 尝试: 74 已通过: 17 难度: 8 上传者: 标签>CF2400提高+/省选-最大边替换深度优先搜索可持久化线段树路径复制历史版本查询二分查找

[Cerc2014]Pork barrel

题目描述

nn 个点 mm 条边有边权的无向图,有 qq 个询问,每次询问权值在 [L,R][L,R] 内的边组成的最小生成树的权值和,强制在线。

输入格式

多组数据,第一行一个整数 TT 表示数据组数。

每组数据的第一行为两个整数 nn 和 mm,接下来 mm 行,每行三个整数 x,y,wx,y,w 表示一条边。

然后一行为一个整数 qq,接下来 qq 行,每行两个整数 L,RL,R ,表示一个询问。

输出格式

共 TT 行,每行一个整数表示最小生成树的权值和。

1
5 7
1 2 2
2 3 4
3 4 3
4 5 1
5 1 3
2 5 4
1 4 5
5
1 2
4 7
11 12
11 13
18 19
3
9
8
14
13

数据范围

对于 100%100\% 的数据,n≤103,m≤105,q≤106n\le 10^3, m\le 10^5, q\le 10^6。