day5上午

清北学堂--刷题班

t1
组合数，

t2

如果询问的重量大于所有的边的权值，那么他的答案是n，每个点都要有，
那么，如果，如果有1条边大于等于这个重量，那么，这条边可以连接两个点，答案n-1，
所以按照询问重量排序，把重量大于等于这个重量的边加入，如果这条边连接的两个点属于两个联通块，那么，联通快的个数--，答案为当前联通块的个数。

正解做法：

还记着货车运输那个题么。
要是只考虑限重的话，其实应该考虑的是原图的最大生成树。
最大生成树有一个性质，任意两点间的边权最小的边一定是连接两点
间所有路径中最大的（否则可以替换，使最大生成树变大）。
这个题目，其实是求最大生成森林的过程，考虑Kruskal 过程，每合并
两个集合，实际上选的这条边是连接两个集合最大的限重。也就是货
物重量低于这个值，就可以通过这条边在两个集合之间运输，否则这
两个集合就一定至少需要两个仓库。
所以整个kruskal 过程，实际上每次是在求，重量低于多少时可以减少
一个仓库。于是一开始有n 个仓库，把减少仓库的关键点记下来，对
于每个询问二分即可。

t3
trie树