BZOJ2286: [Sdoi2011]消耗战【虚树】

题目描述：

题目分析：

虚树除了询问点总数限制，更本质的特征是可以将询问点之间的信息通过dfs预处理出来，从而可以“缩链”。

Code：

#include<bits/stdc++.h>
#define maxn 500005
#define LL long long
using namespace std;
int n,m,k,a[maxn],dep[maxn],fa[maxn],dfn[maxn],tim,siz[maxn],top[maxn],son[maxn];
int fir[maxn],nxt[maxn],to[maxn],w[maxn],tot;
LL mn[maxn];
inline void line(int x,int y,int z){nxt[++tot]=fir[x],fir[x]=tot,to[tot]=y,w[tot]=z;}
bool cmp(int i,int j){return dfn[i]<dfn[j];}
void dfs1(int u,int ff){
    dep[u]=dep[fa[u]=ff]+1,siz[u]=1;
    for(int i=fir[u],v;i;i=nxt[i]) if((v=to[i])!=ff){
        mn[v]=min(mn[u],1ll*w[i]),dfs1(v,u),siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int tp){
    top[u]=tp,dfn[u]=++tim;
    if(son[u]) dfs2(son[u],tp);
    for(int i=fir[u];i;i=nxt[i]) if(!dfn[to[i]]) dfs2(to[i],to[i]);
}
inline int LCA(int u,int v){
    for(;top[u]!=top[v];u=fa[top[u]]) if(dep[top[u]]<dep[top[v]]) swap(u,v);
    return dep[u]<dep[v]?u:v;
}
namespace VTree{
    vector<int>G[maxn];
    int stk[maxn],top,rec[maxn],sz;
    LL dfs(int u){
        if(!G[u].size()) return mn[u];
        LL sum=0;
        for(int i=G[u].size()-1;i>=0;i--) if((sum+=dfs(G[u][i]))>=mn[u]) return mn[u];
        return sum;
    }
    void insert(int x){
        if(top==1) {stk[++top]=x;return;}
        int lca=LCA(stk[top],x);
        if(lca==stk[top]) return;
        while(dfn[lca]<=dfn[stk[top-1]]) G[stk[top-1]].push_back(stk[top]),top--;
        if(lca!=stk[top]) G[lca].push_back(stk[top]),stk[top]=lca,rec[++sz]=lca;
        stk[++top]=x;
    }
    LL solve(){
        while(sz) G[rec[sz--]].clear();
        stk[top=1]=rec[sz=1]=1;
        for(int i=1;i<=k;i++) insert(rec[++sz]=a[i]);
        while(top>1) G[stk[top-1]].push_back(stk[top]),top--;
        return dfs(1);
    }
}
int main()
{
    mn[1]=1ll<<60;
    scanf("%d",&n);
    for(int i=1,x,y,z;i<n;i++) scanf("%d%d%d",&x,&y,&z),line(x,y,z),line(y,x,z);
    dfs1(1,0),dfs2(1,1);
    scanf("%d",&m); 
    while(m--){
        scanf("%d",&k);
        for(int i=1;i<=k;i++) scanf("%d",&a[i]);
        sort(a+1,a+1+k,cmp);
        printf("%lld\n",VTree::solve());
    }
}