P2495 [SDOI2011]消耗战(虚树模板)

题目链接

https://www.luogu.org/problemnew/show/P2495

解题思路

代码

//大意:n个点,有m次询问,每次给出ki个点,
//问割掉这些点的最小花费
#include <bits/stdc++.h>
const int maxn=3e5+100;
const int inf=0x3f3f3f3f;
using namespace std;
int n,m,ki;
int cnt,col,t;
int head[maxn];
int mi[maxn],fa[maxn][20],dep[maxn]
,dfn[maxn],is[maxn],s[maxn];
vector<int>v[maxn];
struct node{
    int v,next,w;
}edge[maxn*2];
void add(int u,int v,int w){
    edge[cnt]={v,head[u],w};
    head[u]=cnt++;
}
bool cmp(int a,int b){
    return dfn[a]<dfn[b];
}
void dfs(int u,int f){
    fa[u][0]=f;
    dfn[u]=++col;
    dep[u]=dep[f]+1;
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==f)
            continue;
        mi[v]=min(mi[u],edge[i].w);
        dfs(v,u);
    }
}
void init(int n){
    for(int j=1;j<=19;j++){
        for(int i=1;i<=n;i++){
            fa[i][j]=fa[fa[i][j-1]][j-1];
        }
    }
}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    int diff=dep[u]-dep[v];
    for(int i=19;i>=0;i--){
        if(diff>>i&1){
            u=fa[u][i];
        }
    }
    if(u==v)return u;
    for(int i=19;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}
int dp(int u){
    if(v[u].size()==0)
        return mi[u];
    int temp=0;
    for(int i=0;i<v[u].size();i++){
        temp+=dp(v[u][i]);
    }
    v[u].clear();
    return min(mi[u],temp);
}
void push(int x){
    if(t==1){
        s[++t]=x;
        return;
    }
    int l=lca(x,s[t]);
    if(l==s[t])
        return;
    while(t>1&&dfn[s[t-1]]>=dfn[l])
        v[s[t-1]].push_back(s[t]),t--;
    if(s[t]!=l)
        v[l].push_back(s[t]),s[t]=l;
    s[++t]=x;
}
int main()
{
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    mi[1]=inf;
    dfs(1,0);
    cin>>m;
    init(n);
    while(m--){
        cin>>ki;
        for(int i=1;i<=ki;i++){
            cin>>is[i];
        }
        sort(is+1,is+ki+1,cmp);
        s[t=1]=1;
        for(int i=1;i<=ki;i++){
            push(is[i]);
        }
        while(t>0)
            v[s[t-1]].push_back(s[t]),--t;
        cout<<dp(1)<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注