虚树学习笔记

这个知识点不是很难，其实就是一类特殊的树形dp：这类dp会有多次询问，每次询问给出一个点集合S然后这次询问的内容只与集合S的点相关。

学习博客：https://blog.csdn.net/ouqingliang/article/details/81669281

https://blog.csdn.net/zhouyuheng2003/article/details/79110326

假如树的大小为n，询问个数问m，如果对于每次询问都在整棵树做树形dp，那么时间复杂度是O(n*m)，TLE。但是我们注意到所有询问的点总数比较小。于是我们想其实每次dp不需要把整棵树dp，把S集合点建立一棵虚树然后在这棵虚树上dp即可。

所以这个知识点的重点就是怎么求集合S的虚树？把点集按dfn排序，用一个栈表示虚树上从根到当前点的路径，然后通过比较栈元素的dfn和当前点x的dfn来建立虚树。上面两位大佬博客已经把过程说得很清楚了，画图仔细想一下就能明白。

题目练习：

这个算法重点是怎么建立虚树，具体求解的dp过程还是具体分析。

洛谷P3320

发现对于一次询问代价其实就是dist(a1,a2)+dist(a2,a3)+...dist(an,a1) (ai要按dfn排序)。问题是这道题的点是动态添加删除的，怎么办呢？发现其实添加一个点x，x的dfn前缀是l，x的dfn后缀是r，对答案的新增贡献就是dist(l,x)+dist(x,r)-dist(l,r)。删除同理。那么我们就可以用set维护当前点集，然后通过LCA快速算新增贡献即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n,m,t;
set<int> S;
set<int>::iterator it;

int cnt=1,head[N],nxt[N<<1],to[N<<1],len[N<<1];
void add_edge(int x,int y,int z) {
    nxt[++cnt]=head[x]; to[cnt]=y; len[cnt]=z; head[x]=cnt;
}

int num=0,dfn[N],idx[N],dep[N],f[N][20]; LL dis[N];
void dfs(int x,int fa) {
    dfn[x]=++num; idx[num]=x; dep[x]=dep[fa]+1;
    for (int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        if (!dfn[y]) {
            dis[y]=dis[x]+len[i];
            f[y][0]=x;
            for (int j=1;j<=t;j++) f[y][j]=f[f[y][j-1]][j-1];
            dfs(y,x);
        }
    }
}

int lca(int x,int y) {
    if (dep[x]<dep[y]) swap(x,y);
    for (int i=t;i>=0;i--)
        if (dep[f[x][i]]>=dep[y]) x=f[x][i];
    if (x==y) return x;
    for (int i=t;i>=0;i--)
        if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];    
    return f[x][0];    
}

LL dist(int x,int y) { return dis[x]+dis[y]-2*dis[lca(x,y)]; }

int main()
{
    cin>>n>>m;
    t=log(n)/log(2)+1;
    for (int i=1;i<n;i++) {
        int x,y,z; scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,z); add_edge(y,x,z);
    }
    dfs(1,0);
    LL ans=0;
    for (int i=1;i<=m;i++) {
        int x,l,r; scanf("%d",&x);
        if (!S.count(dfn[x])) {  //插入操作 
            S.insert(dfn[x]);
            it=S.lower_bound(dfn[x]); if (it==S.begin()) l=*--S.end(); else l=*--it;
            it=S.upper_bound(dfn[x]); if (it==S.end()) r=*S.begin(); else r=*it;
            l=idx[l]; r=idx[r];
            ans+=dist(l,x)+dist(x,r)-dist(l,r);
        } else {  //删除操作 
            it=S.lower_bound(dfn[x]); if (it==S.begin()) l=*--S.end(); else l=*--it;
            it=S.upper_bound(dfn[x]); if (it==S.end()) r=*S.begin(); else r=*it;
            l=idx[l]; r=idx[r];
            ans-=dist(l,x)+dist(x,r)-dist(l,r);
            S.erase(dfn[x]);
        }
        printf("%lld
",ans);
    }
    return 0;
}

View Code

洛谷P2495

建立虚树。然后dp[x]=min(dp[x],sigma(dp[y])) (y是x的儿子)。写了可以当虚树模板。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+10;
const LL INF=1LL<<60;
int n,m,k,t,a[N]; 

int cnt=1,head[N],nxt[N<<1],to[N<<1],len[N<<1];
void add_edge(int x,int y,int z) {
    nxt[++cnt]=head[x]; to[cnt]=y; len[cnt]=z; head[x]=cnt;
}

//-------------------------------LCA------------------------------
int num=0,dfn[N],idx[N],dep[N],f[N][20]; LL Min[N];
void dfs(int x,int fa) {
    dfn[x]=++num; idx[num]=x; dep[x]=dep[fa]+1;
    for (int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        if (!dfn[y]) {
            Min[y]=min(Min[x],(LL)len[i]);
            f[y][0]=x;
            for (int j=1;j<=t;j++) f[y][j]=f[f[y][j-1]][j-1];
            dfs(y,x);
        }
    }
}

int LCA(int x,int y) {
    if (dep[x]<dep[y]) swap(x,y);
    for (int i=t;i>=0;i--)
        if (dep[f[x][i]]>=dep[y]) x=f[x][i];
    if (x==y) return x;
    for (int i=t;i>=0;i--)
        if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];    
    return f[x][0];    
}

bool cmp(int x,int y) { return dfn[x]<dfn[y]; }

//-------------------------------虚树------------------------------ 
vector<int> G[N];  //得到的虚树 
int sk[N<<1],top=1;  //栈:从根到当前点的路径 

void Insert(int x) {
    if (top==1) { sk[++top]=x; return; }
    int lca=LCA(x,sk[top]);
    if (lca==sk[top]) return;
    while (top>1 && dfn[sk[top-1]]>=dfn[lca])
        G[sk[top-1]].push_back(sk[top]),top--;
    if (lca!=sk[top]) G[lca].push_back(sk[top]),sk[top]=lca;
    sk[++top]=x;    
}

void Build() {
    sk[top=1]=1;  //先把根插入到栈 
    for (int i=1;i<=k;i++) Insert(a[i]);  //逐个点插入到虚树 
    for (;top;top--) G[sk[top-1]].push_back(sk[top]);  //把剩下点连边得到完整虚树 
}

//-------------------------------DP------------------------------ 
LL dp_dfs(int x) {
    if (G[x].size()==0) return Min[x];
    LL ret=0;
    for (int i=0;i<G[x].size();i++) {
        int y=G[x][i];
        ret+=dp_dfs(y);
    }
    G[x].clear();  //关键：边dp边删除虚树，外部删除会TLE。 
    return min(ret,Min[x]);
}

int main()
{
    cin>>n;
    t=log(n)/log(2)+1;
    for (int i=1;i<n;i++) {
        int x,y,z; scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,z); add_edge(y,x,z);
    }
    Min[1]=INF;
    dfs(1,0);  //倍增求LCA预处理 
    
    cin>>m;
    for (int i=1;i<=m;i++) {
        scanf("%d",&k);
        for (int j=1;j<=k;j++) scanf("%d",&a[j]);
        sort(a+1,a+k+1,cmp);
        Build();  //建立k个点的虚树 
        printf("%lld
",dp_dfs(1));  //在虚树上dp求出答案 
    }
    return 0;
}

View Code

洛谷P3233