洛谷 - P2495 [SDOI2011]消耗战

传送门：洛谷 - P2495

思路分析

设$dp[x]$表示$x$到根节点的最小边
建立虚树步骤：
对于每个询问节点，按照$dfs$序排序
维护一个栈，表示从根节点到栈顶的链
考虑新加入一个节点$p$，当前栈顶$x$，$p$和$x$的最近公共祖先$lca$

1. $x$就是$lca$，则$p$在子树内，$p$直接加入栈
2. $x$不是$lca$，则$p$不在$x$的子树中，不断连接栈内的边，直到栈顶的$dfs$序小于等于$lca$

如果栈顶不是$lca$，则先将$lca$与栈顶连边，栈顶替换为$lca$，再加入$p$

对于这道题的话，因为子树的代价会被覆盖，所以在子树中的话就直接返回

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N = 1e6+10;
#define int long long
vector<pair<int,int>>e[N];
int dep[N],f[N],top[N],son[N],siz[N],dp[N],dfn[N],tim;

void dfs1(int u,int fa) {
    dep[u]=dep[fa]+1;
    siz[u]=1;
    son[u]=0;
    f[u]=fa;
    for(auto x:e[u]) {
        int v = x.fi;
        int w = x.se;
        if(v==fa) continue;
        dp[v]=min(dp[u],w);
        
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}

void dfs2(int u,int t) {
    top[u]=t;
    dfn[u]=++tim;
    if(!son[u]) return ;
    dfs2(son[u],t);
    for(auto x:e[u]) {
        int v=x.fi;
        if(v==f[u] || v==son[u]) continue;
        dfs2(v,v);
    }
}

int getlca(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 x;
}

vector<int>new_e[N];
int st[N],Top;

void add(int u,int v){
    new_e[u].pb(v);
}

void insert(int x) {
    if(Top <= 1) {
        st[++Top] = x;
        return ;
    }
    int lca = getlca(x, st[Top]);
    if(lca == st[Top]) return ;
    while(Top > 1 && dfn[st[Top - 1]] >= dfn[lca]) {
        add(st[Top - 1], st[Top]);
        --Top;
    }
    if(lca != st[Top]) add(lca, st[Top]), st[Top] = lca;
    st[++Top] = x;
}

int DP(int u){
    if(sz(new_e[u])==0) return dp[u];
    int sum=0;
    for(auto v:new_e[u]) {
        sum+=DP(v);
    }
    new_e[u].clear();
    return min(sum,dp[u]);
    
}

signed main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n,q;
    read(n);
    for(int i=1; i<n; i++) {
        int u,v,w;
        read(u,v,w);
        e[u].pb(mp(v,w));
        e[v].pb(mp(u,w));
    }
    mem(dp,INF);
    dfs1(1,0);
    dfs2(1,1);
    read(q);
    while(q--) {
        int m;
        vector<int>tmp;
        tmp.pb(1);
        read(m);
        for(int i=1; i<=m; i++) {
            int x;
            read(x);
            tmp.pb(x);
        }
        sort(all(tmp),[](int x,int y) {
            return dfn[x]<dfn[y];
        });
        
        Top=0;
        for(auto i:tmp) insert(i);
        while(Top>1){
            add(st[Top-1],st[Top]);
            --Top;
        }
        
        printf("%lld\n",DP(1));

    }




    return 0;
}