bzoj 2286 [Sdoi2011]消耗战 虚树+dp

时间：2023-12-10 16:31:56

题目大意：多次给出关键点，求切断边使所有关键点与1断开的最小费用

分析：每次造出虚树,dp[i]表示将i和i子树与父亲断开费用

对于父亲x，儿子y

①y为关键点：\(dp[x]\)+=\(dismn(x,y)\)

②y不为关键点：要么断y，要么断y所有子树

\(dp[x]\)+=\(min(dismn(x,y),dp[y])\)

=========================================================

关于兼容性的一种讨论

dismn(x,y)直接改为dismn(1,x)预处理算可以吗

当然不行？

交一发,A

兼容性：若要算到y，则y到1路径中没有关键点

①情况无影响

②情况中若子树中最小值算到了上面，断y定更优，而断y又变成父节点的①②情况讨论

所以是可以的咯

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
using namespace std;
typedef long long LL;
const int M=250007;
inline int rd(){
    int x=0;bool f=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=0;
    for(;isdigit(c);c=getchar())x=x*10+c-48;
    return f?x:-x;
}

int n,m;

LL dp[M];
LL dis[M];
LL w[M][20];
int ln[M];

int dep[M],sz[M],son[M],pre[M];
int top[M],dfn[M],pid[M],T;

int que[M],kd[M];
bool cmp(int x,int y){return dfn[x]<dfn[y];}
int st[M],tot;

int g[M],te;
struct edge{int y,next;LL d;}e[M<<1];
void addedge(int x,int y,LL d){
    e[++te].y=y;e[te].d=d;e[te].next=g[x];g[x]=te;
}

int hd[M],td;
struct link{int y,next;}dw[M];
void addlink(int x,int y){
    if(x==y)return;
    dw[++td].y=y;dw[td].next=hd[x];hd[x]=td;
}

void dfs1(int x){
    sz[x]=1;
    int p,y;
    for(p=g[x];p;p=e[p].next)
    if((y=e[p].y)!=pre[x]){
        dep[y]=dep[x]+1;
        dis[y]=e[p].d;
        pre[y]=x;
        dfs1(y);
        sz[x]+=sz[y];
        if(sz[y]>sz[son[x]]) son[x]=y;
    }
}

void dfs2(int x){
    pid[dfn[x]=++T]=x;
    if(son[x]){
        top[son[x]]=top[x];
        dfs2(son[x]);
    }
    int p,y;
    for(p=g[x];p;p=e[p].next)
    if((y=e[p].y)!=pre[x]&&y!=son[x]){
        top[y]=y;
        dfs2(y);
    }
}

int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=pre[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    return x;
}

void vbuild(int z){
    int i,x,anc;
    sort(que+1,que+z+1,cmp);
    for(i=1;i<z;i++){
        anc=LCA(que[i],que[i+1]);
        hd[anc]=0; kd[anc]=2; dp[anc]=0;
    }
    hd[1]=0; dp[1]=0;//*****
    for(i=1;i<=z;i++){
        x=que[i];
        hd[x]=0; kd[x]=1; dp[x]=0;
    }
    td=0;
    tot=0;
    st[++tot]=1;
    for(i=1;i<=z;i++){
        x=que[i];
        anc=LCA(x,st[tot]);
        if(anc==st[tot]){
            st[++tot]=x;
            continue;
        }
        else{
            while( tot>1 && dep[anc]<=dep[st[tot-1]]){
                addlink(st[tot-1],st[tot]);
                tot--;
            }
            addlink(anc,st[tot]);
            st[tot]=anc;
            st[++tot]=x;
        }
    }
    for(i=1;i<tot;i++) addlink(st[i],st[i+1]);
}

LL getm(int x,int y){
    int l=ln[y-x+1];
    return min(w[x][l],w[y-(1<<l)+1][l]);
}

void init(){
    int i,j,l;
    for(i=2;i<=n;i++) ln[i]=ln[i>>1]+1;
    for(i=1;i<=n;i++) w[i][0]=dis[pid[i]];
    for(i=n;i>0;i--){
        l=ln[n-i+1];
        for(j=1;j<=l;j++) w[i][j]=min(w[i][j-1],w[i+(1<<j-1)][j-1]);
    }
}

LL getw(int x,int y){
    LL res=1LL<<61;
    while(dep[top[x]]>dep[y]){
        res=min(res,getm(dfn[top[x]],dfn[x]));
        x=pre[top[x]];
    }
    if(x!=y) res=min(res,getm(dfn[y]+1,dfn[x]));
    return res;
}

void dfs(int x){
    int p,y;
    LL tp;
    for(p=hd[x];p;p=dw[p].next){
        y=dw[p].y;
        tp=getw(y,x);
        if(kd[y]==1) dp[x]+=tp;
        else{
            dfs(y);
            dp[x]+=min(tp,dp[y]);
        }
    }
}

int main(){
    int i,x,y,z;
    n=rd();
    for(i=1;i<n;i++){
        x=rd(),y=rd(),z=rd();
        addedge(x,y,z);
        addedge(y,x,z);
    }

    dep[1]=pre[1]=0;
    dis[1]=0;
    dfs1(1);
    top[1]=1;
    dfs2(1);

    init();

    m=rd();
    while(m--){
        z=rd();
        for(i=1;i<=z;i++) que[i]=rd();
        vbuild(z);
        dfs(1);
        printf("%lld\n",dp[1]);
    }
    return 0;
}

相关文章