刚过这道题,用的是树剖+st表

甚至拿了最优解

有一点不明白的是:

此题题干没有说明保证初始的图连通,那么其实固定从某个结点(比题解区的几篇树剖题解把1作为根节点)开始DFS的树剖和树上倍增都是能卡掉的.

例如如下数据:

4 2
1 2 10
3 4 10
1
3 4

在查询时,由于3,4结点没有被dfs到,也不会被线段树或者倍增数组维护,这能够算作一种hack数据的构造方式吗?

以及,如果这样的数据是不可行的的,那么是不是应该在题目描述内加上"保证初始图连通"?

否则就要考虑维护森林的每棵树了.