icontofig | 发布于 2020-07-12 22:40:20 | 阅读量 193 | DP 虚树
发布于 2020-07-12 22:40:20 | DP 虚树

 

题解

本人的虚树入门题。

基础思想

题目意思相当于m次询问,每次询问给出一些点,要我们付出一定代价断边使得给出的这些点与根节点1不连通.

首先肯定能确定这个题是一个树形DP。转移方程也非常好写。

考虑对于单次询问,我们设f[x]为处理完以x为子树的最小的代价。

那么转移无非是两种情况:

1.断开与父亲的连接,代价为从x到根1的路径上的最小值。

2.当该点不是询问点的时候,把子树内所有询问点都与根节点断开的代价。

但是这样有一个问题,每次询问都是O(n)的,来看一下数据范围:

很明显O(nm)的做法是无法处理的。

进阶优化 & 虚树的引出

但实际上,我们在对每一次询问的处理中,考虑了很多无用点的信息。

考虑一下,很容易能够明白,实际上,只有询问点、其LCA、其LCA的LCA及其三次LCA……等,对这些点和上面的根进行断开是实际在最小答案中有效的,处理其他的点实际上无效。

所以虚树就应运而生了。

虚树是主要运用在树形DP中的一类构造方法,旨在只将对答案有用的点拿出来构造一棵虚拟的新的树,以此来降低算法的复杂度。

举个栗子,在本题的样例中有这样的数据。

对于样例中的询问数据

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

其对应的虚树分别是以下的形式

第二个询问中,由于点7、8均在5的子树内,故断开5以及根节点的连接即可,7、8实际上是无用点(仅对此题而言,不同题目要考虑不同的构造)

虚树的构建

现在需要考虑的是如何构建虚树。

首先我们要先对整棵树dfs一遍,求出他们的dfs序,然后对每个节点以dfs序为关键字从小到大排序(本人比较喜欢用树链剖分里面的那种形式)

同时维护一个栈,表示从根到栈顶元素这条链

假设当前要加入的节点为pp,栈顶元素为x=s[top]x=s[top]lcalca为他们的最近公共祖先

因为我们是按照dfs序遍历,因此lcalca不可能是pp

那么现在会有两种情况

  1. lcalcaxx,直接将pp入栈。
  2. x,px,p分别位于lcalca的两棵子树中,此时xx这棵子树已经遍历完毕,(如果没有,即x的子树中还有一个未加入的点y,但是dfn[y]<dfn[p],即应先访问y), 我们需要对其进行构建

设栈顶元素为xx,第二个元素为yy

  • dfn[y]>dfn[lca]dfn[y]>dfn[lca],可以连边y>xy−>x,将xx出栈;
  • dfn[y]=dfn[lca]dfn[y]=dfn[lca],即y=lcay=lca,连边lca>xlca−>x,此时子树构建完毕(break);
  • dfn[y]<dfn[lca]dfn[y]<dfn[lca],即lcalcay,xy,x之间,连边lca>xlca−>xxx出栈,再将lcalca入栈。此时子树构建完毕(break)。

此处较为抽象,建议大家画图理解一下
不断重复这个过程,虚树就构建完成了,另外我们需要维护出链上的最小值,然后我们直接在虚树上dp就可以了

 

最终的复杂度为O(2*Σki)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5+5;
struct edge{
    int u,v,next;
    ll w;
}e[maxn<<2];
int h[maxn];
int cnt = 0;
void add(int u,int v,ll w){
    e[cnt].u = u;e[cnt].v = v;e[cnt].w = w;
    e[cnt].next = h[u];h[u] = cnt++;
    return;
}
int q[maxn];
int n,m;
vector<int>g[maxn];
int top[maxn],siz[maxn],son[maxn],id[maxn],f[maxn],dep[maxn],dfs_time = 0,s[maxn],tp;
ll min_w[maxn];
void dfs(int now,int fa,int depth){
    siz[now] = 1;
    f[now] = fa;
    dep[now] = depth;
    for(int i = h[now];i != -1;i = e[i].next){
        int to = e[i].v;
        if(to == fa)continue;
        min_w[to] = min(min_w[now],e[i].w);
        dfs(to,now,depth+1);
        siz[now] += siz[to];
        if(siz[to] > siz[son[now]])
            son[now] = to;
    }
    return;
}
void get_id(int now,int topf){
    top[now] = topf;
    id[now] = ++dfs_time;
    if(son[now])
        get_id(son[now],topf);
    for(int i = h[now];i != -1;i = e[i].next){
        int to = e[i].v;
        if(to == f[now] || to == son[now])continue;
        get_id(to,to);
    }
    return;
}
int lca(int x,int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])swap(x,y);
        x = f[top[x]];
    }
    if(dep[x] < dep[y])swap(x,y);
    return y;
}
void insert(int now){
    if(tp == 1){
        s[++tp] = now;
        return;
    }
    int fa = lca(now,s[tp]);
    if(fa == s[tp])return;//本题特殊
    while(tp > 1 && id[s[tp-1]] >= id[fa]){
        g[s[tp-1]].push_back(s[tp]);
        tp--;
    }
    if(fa != s[tp]){
        g[fa].push_back(s[tp]);
        s[tp] = fa;
    }
    s[++tp] = now;
    return;
}
ll dp(int now){
    if(g[now].size() == 0)return min_w[now];
    ll res = 0;
    for(auto it : g[now])
        res += dp(it);
    g[now].clear();
    return min(res,min_w[now]);
}
bool cmp(int a,int b){
    return id[a] < id[b];
}
int u,v,w,k;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(h,-1,sizeof(h));
    cin >> n;
    min_w[1] = 1ll<<60;
    for(int i = 1;i < n;++i){
        cin >> u >> v >> w;
        add(u,v,w);add(v,u,w);
    }
    dfs(1,0,0);
    get_id(1,1);
    cin >> m;
    while(m--){
        cin >> k;
        for(int i = 1;i <= k;++i){
            cin >> q[i];
        }
        sort(q+1,q+k+1,cmp);
        tp = 1;
        s[tp] = 1;
        for(int i = 1;i <= k;++i)
            insert(q[i]);
        while(tp){
            g[s[tp-1]].push_back(s[tp]);
            tp--;
        }
        cout << dp(1) << "\n";
    }
    return 0;
}

 本文部分转自自为风月马前卒的博客,大佬写的太好了,感觉讲的真的很好,所以引用了一下,此处注明以尊重大佬的著作权。


内容更新于: 2020-07-12 22:40:20
链接地址: http://blog.leanote.com/post/icontofig/Luogu-P2495-%5BSDOI2011%5D%E6%B6%88%E8%80%97%E6%88%98

上一篇: 无

下一篇: ZOJ 4086 Little Sub and a Game 线性基博弈

193 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航