#P4252. mx的仙人掌

    ID: 3469 传统题 2000ms 512MiB 尝试: 33 已通过: 12 难度: 9 上传者: 标签>CF2800省选/NOI-仙人掌图圆方树虚树DFS 序排序补充相邻点 LCA树上倍增树形 DP复制数组处理环单调队列稀疏状态重置

mx的仙人掌

题目描述

如果一个无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

现给定一棵仙人掌,每条边有一个正整数权值,每次给 kk 个点(可以存在相同点),问从它们中选出两个点(可以相同),它们之间最短路的最大值是多少。

输入格式

第一行两个非负整数 n,mn, m,表示仙人掌的点数和边数。

接下来 mm 行,每行三个正整数 v,u,wv,u,w(1≤v,u≤n1 \le v,u \le n),表示 vv 与 uu 之间有一条边权为 ww 的无向边。点从 11 开始编号。

保证输入的图是一棵仙人掌,保证没有自环,但可能有重边。

接下来一行一个非负整数 QQ,表示询问个数。

接下来 QQ 行每行第一个数是正整数 cntcnt 表示点数,接下来 cntcnt 个数表示给定的点。

输出格式

对每个询问输出一个数,表示该询问对应的最大值。

样例输入

10 14
10 7 1
3 8 7
1 6 9
7 2 10
8 9 9
1 7 1
8 5 2
4 5 4
1 7 4
2 9 8
9 3 3
8 4 2
1 6 5
7 9 10
6
2 9 5
2 8 10
3 8 7 6
2 6 4
3 3 4 2
1 10

样例输出

11
20
25
27
19
0

数据规模与约定

前五个询问的答案路径分别为(如果有重边则显然走较短的边):

9→8→59 \rightarrow 8 \rightarrow 5,

8→9→7→108 \rightarrow 9 \rightarrow 7 \rightarrow 10,

$8 \rightarrow 9 \rightarrow 7 \rightarrow 1 \rightarrow 6$,

$4 \rightarrow 8 \rightarrow 9 \rightarrow 7 \rightarrow 1 \rightarrow 6$,

2→9→8→42 \rightarrow 9 \rightarrow 8 \rightarrow 4,

最后一个询问的答案显然是 00。

边权不超过 231−12^{31}−1。

对于 100%100\% 的数据,1≤n,tot≤3×1051 \le n,tot \le 3 \times 10 ^ 5。

题目来源

By matthew99