虚树学习笔记

Butterfly_qwq · 2023-05-29 22:01:44 · 算法·理论

有一个n个结点的树，根为1。

对于m次询问，每次给定k个关键点，需要选定一些边断开（每条边有断开的代价），使得1号点和k个点中的任意结点都不连通。求满足要求的最小代价。

保证给定的k个关键点中一定不包含1号点

注：\Sigma k即为所有k之和

朴素想法树形DP，在此略过

如何优化？

我们可以发现有许多点是无用的

注：没有4，请不要在意 如这棵树，若 8,10,12,16,17是关键点，那么只有如下的点和边有用

显然简化了不少。

那如何构造这样一颗树呢？

1. 所有关键点以dfn排序
2. 两两求出LCA
3. 将所有LCA和点1插入虚树的点数组，然后按dfn排序后去重
4. 再次两两求LCA，将两个点中dfn较大的点与求出来的LCA连线

做完了

Code：

bool cmp(int x, int y) {//按照 dfn 序排序
    return dfn[x] < dfn[y];
}
void build() {
    int len=0;
    sort(h + 1, h + k + 1, cmp);  //输入的关键点
    for(int i = 1; i < k; i++) {
        a[++len] = h[i];
        a[++len] = lca(h[i], h[i + 1]);  //插入 lca
    }
    a[++len] = h[k]; a[++len] = 1;
    sort(a + 1, a + len + 1, cmp);  //把所有虚树上的点按照 dfn 序排序
    len = unique(a + 1, a + len + 1) - a - 1;  //去重
    for (int i = 1, lc; i < len; i++) {
        lc = lca(a[i], a[i + 1]);
        add(lc, a[i + 1]);  //连边
    }
}

注：不是我写的，但是有错还是找我的洛谷账号 @FeS2_qwq（或直接联系@babyec 虽然我很不建议你这样干）

但是，别忘了我们还有边权！！！新边权怎么办？

别着急，我们有只用老边权处理新图的方案。

设minw_i为1到i之间的最短边权，若i为关键点，则必须与点1断开dp_i=minw_i

否则，则i既可以和点1断开，也可以和下面的关键点断开dp_i=\min(minw_i,\Sigma dp_j)

注：\Sigma dp_j就是所有i的儿子的dp值之和

哦，漏了一点，时间复杂度 O(\Sigma k\log n)，大概算了一下，上面的问题可以\le90\operatorname{ms}的时间完成（？

然后大概就做完了吧。

模板题

纯纯的模板啊！！！

该文同步发表于