虚树学习小结

从一道模板题说起

• 一道模板题：[SDOI2011]消耗战
• 一个显然的东西，设f(x)表示x子树内的点不能通过x走到根最小代价。如果x不是特殊点，f(x)=min(m[x],$\sum$∑f(son[x]))，否则f(x)=m[x]（其中m[x]表示x到根路径上的最短边），然而会T
• 但是我们发现，有很多点是根本没有卵用的。同时，有用的转移，要么是他们本身，要么是几个不存在父子关系的结点的lca，当然m还是非常有卵用的。
• 于是一个牛逼的东西诞生了——虚树
• 虚树的构造
• 设dfn[x]表示x对应dfs序编号，并按照dfn从小到大加入
• 对于我们加入的这个点x，设l为它与栈顶的lca
• dfn[l]=dfn[s[top]],那么我们可以知道，x肯定是跟栈顶那个点是在同一条链上的（值得注意的是，在这题目中如果有两个点都是特殊点，并且有一个是另一个的父亲，那么那个儿子就没用了，也就是说在这道题里，我们不需要加入）。
• 否则，我们可以知道x跟s[top]分别是lca下面的两棵不同的子树，说明前面的那一条链已经弄完了，出栈的过程中，同时连边，最后，判断l是否在栈中，如果不在，将它加入栈，并且连边，最后加入x
• 注意，将所有点加完之后，栈里面还有一条链，记得要弹出连边。
• code（我感觉luogu的数据有些奇怪，c不是小于等于100000吗）

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define Fo(i,x) for (int i=head[x];i;i=next[i])
using namespace std;
const int N=250000+255;
typedef long long ll;
int head[N],to[N*2],next[N*2],w[N*2],n,T,cnt,s[N],k,tot,x,y,z;
int size[N],fa[N],d[N],top[N],son[N],dfn[N],a[N];
ll m[N];
void add(int x,int y){
    to[++tot]=y;
    next[tot]=head[x];
    head[x]=tot;
}
void dfs(int x){
    size[x]=1;
    Fo(i,x){
        int v=to[i];
        if (v==fa[x]) continue;
        m[v]=min((ll)w[i],m[x]);fa[v]=x;d[v]=d[x]+1;
        dfs(v);
        size[x]+=size[v];
        if (size[son[x]]<size[v]) son[x]=v;
    }
}
void Dfs(int x,int T){
    dfn[x]=++cnt;
    top[x]=T;
    if (son[x]) Dfs(son[x],T);else return;
    Fo(i,x){
        int v=to[i];
        if (v==fa[x]||v==son[x]) continue;
        Dfs(v,v);
    }
}
int lca(int x,int y){
    while (top[x]!=top[y]){
        if (d[top[x]]<d[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return d[x]<d[y]?x:y;
}
void ins(int x){
    if (k==1) { s[++k]=x; return; }
    int l=lca(s[k],x);
    if (l==s[k]) return;
    while (k>1&&dfn[s[k-1]]>=dfn[l]) add(s[k-1],s[k]),k--;
    if (s[k]!=l) add(l,s[k]),s[k]=l;
    s[++k]=x;
}
ll dp(int x){
    if (!head[x]) return (ll)m[x];
    ll s=0;
    Fo(i,x){
        s+=dp(to[i]);
    }
    head[x]=0;
    return min(s,(ll)m[x]);
}
bool cmb(int a,int b){
    return dfn[a]<dfn[b];
}
int main(){
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    scanf("%d",&n);
    fo(i,1,n-1) {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y);w[tot]=z;
        add(y,x);w[tot]=z;
    }
    m[1]=1ll<<60;
    dfs(1);
    Dfs(1,1);
    memset(head,0,sizeof(head));
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n); 
        tot=0;
        fo(i,1,n) scanf("%d",&a[i]);
        sort(a+1,a+n+1,cmb);
        s[k=1]=1;
        fo(i,1,n) ins(a[i]);
        while (k) add(s[k-1],s[k]),k--;
        printf("%lld\n",dp(1));
    } 
    return 0;
}

坑：
[HNOI2014]世界树
[SDOI2015]寻宝游戏
[HEOI2014]大工程
…
感觉这是一个天坑。