虚树（树形dp套路）模板——bzoj2286

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 200005
struct Edge{int u,to,w,nxt;}e[maxn<<1];
int head[maxn],tot;
void add(int u,int v,int w){
}

vector<int>v[maxn];
void add_edge(int x,int y){v[x].push_back(y);}

int a[maxn],dfn[maxn],top[maxn],size[maxn],son[maxn],s[maxn],deep[maxn],fa[maxn];
int tp,ind,n,m;
ll Min[maxn];
void dfs1(int x,int pre){
    size[x]=1;fa[x]=pre;
    for(int i=head[x];i!=-1;i=e[i].nxt){
        int y=e[i].to;
        if(y==pre)continue;
        deep[y]=deep[x]+1;
        Min[y]=min(Min[x],(ll)e[i].w);
        dfs1(y,x);
        size[x]+=size[y];
        if(size[y]>size[son[x]])
            son[x]=y;
    }
}
void dfs2(int x,int tp){
    top[x]=tp;dfn[x]=++ind;
    if(!son[x])return;
    dfs2(son[x],tp);
    for(int i=head[x];i!=-1;i=e[i].nxt){
        int y=e[i].to;
        if(!top[y])
            dfs2(y,y);
    }
}
int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]])
            swap(x,y);
        x=fa[top[x]];
    }
    if(deep[x]<deep[y])swap(x,y);
    return y;
}

int cmp(int a,int b){return dfn[a]<dfn[b];} 

void insert(int x){//往栈中加入新的结点 
    if(tp==1){s[++tp]=x;return;}//如果栈里只有一个根节点，那么直接入栈即可 
    int lca=LCA(x,s[tp]); //求出x和栈顶元素的lca
    if(lca==s[tp])return;//这里本来是要将x入栈的，但是由于本题特殊条件，选择了lca等价于选择x，所以可以既然lca在栈 中直接忽略x
    while(tp>1 && dfn[s[tp-1]]>=dfn[lca])//这里是栈的第二个元素还在lca下面，所以继续出栈，连边 
        add_edge(s[tp-1],s[tp]),tp--;
    if(lca!=s[tp])//第二元素在lca上面，栈顶出栈，压入lca(即lca必选) 
        add_edge(lca,s[tp]),s[tp]=lca;
    s[++tp]=x; //最后把x入栈 
}

ll DP(int x){//在虚树上进行dp，找到最优解 
    if(v[x].size()==0)return Min[x];
    ll sum=0;
    for(int i=0;i<v[x].size();i++)
        sum+=DP(v[x][i]);
    v[x].clear();
    return min(sum,(ll)Min[x]);//要么切断所有x子节点，要么切断x到fa[x]的边 
}

int main(){
    memset(head,-1,sizeof head);
    Min[1]=(ll)1<<60;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);add(y,x,z);
    }
    deep[1]=1;
    dfs1(1,0);dfs2(1,1);
    
    cin>>m;
    while(m--){
        int k;
        scanf("%d",&k);
        for(int i=1;i<=k;i++)scanf("%d",&a[i]);
        sort(a+1,a+1+k,cmp);//把点按照dfs序排列 
        s[++tp]=1;//根节点1入栈 
        for(int i=1;i<=k;i++)
            insert(a[i]);
        while(tp>0)//把剩下的点进行连边 
            add_edge(s[tp-1],s[tp]),tp--;
        printf("%lld\n",DP(1));
    }
    return 0;
}