题意:求树上第k大联通块 n,k<=1e5
考虑转化为k短路的形式。
也就是要建出一张图是的这条图上每一条S到T的路径都能代表一个联通块。
点分治建图
递归下去,假定每个子树的所有联通块中都可以被表示为一条s'--->t'的路径。
合并的时候新建关于当前分治重心的S点和T点。
S->s1->t1->s2->t2-s3->t3->T。
其中S->s1边权为wx,ti->si+1的边权为0,再连一条S->T边权为0代表这个点不选的方案即可。
这样一波神仙操作后S->T就可以代表一条选择了这个点(这里选择的意思是最终联通块包含这个点)的一个联通块。
最后再建立S和T,S向所有源点连边,T向所有汇点连边即可(边权为0)。
这样S到T的一条路径即可代表一个树上的联通块。
然后再这个图上跑k短路即可。
复杂度显然取决于点数,而这个点数又显然与点分治复杂度同阶----O(nlogn)。
代码?我也不会写啊qwq

04-28 00:47