BZOJ_2286_[Sdoi2011]消耗战_虚树+树形DP+树剖lca

时间：2021-03-17 20:19:40

BZOJ_2286_[Sdoi2011]消耗战_虚树+树形DP

Description

在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到1号岛屿上）。不过侦查部门还发现了这台机器只能够使用m次，所以我们只需要把每次任务完成即可。

Input

第一行一个整数n，代表岛屿数量。

接下来n-1行，每行三个整数u,v,w，代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连，保证1<=u,v<=n且1<=c<=100000。

第n+1行，一个整数m，代表敌方机器能使用的次数。

接下来m行，每行一个整数ki，代表第i次后，有ki个岛屿资源丰富，接下来k个整数h1,h2,…hk，表示资源丰富岛屿的编号。

Output

输出有m行，分别代表每次任务的最小代价。

Sample Input

10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6

Sample Output

12
32
22

HINT

对于100%的数据，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1

如果询问只有一次，我们可以想出DP做法。

首先将边权下放到点权上，设F[i]表示i的子树中所有资源都被切断的最小代价。

如果i这个点是资源，则f[i]=代价val[i]。

否则f[i]=min(g[i],子树f[to]和)。

但这样每次做是O(n)的。

考虑实际上不是每条边都会用到。

我们先处理出g[x]表示从x到根的最短的代价，用这个代替val[x]显然是可行的。

这样我们就不需要存全部的点。

考虑重新建一棵树，其中包含所有点和他们的lca。

用一个栈来维护一条链，每次保证栈中的是一条链，否则弹栈，弹栈的同时连边。

方法：每次求出当前点和栈顶的lca，一直弹栈直到栈顶的深度小于等于lca的深度。

然后最后对剩余栈中的点连边。栈底元素就是lca中深度最小的一个。DP即可。

注意每次连边后head要清。

代码：

#include <cstdio>

#include <string.h>

#include <algorithm>

using namespace std;

typedef long long ll;

inline char nc() {

    static char buf[100000],*p1,*p2;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

int rd() {

    int x=0; char ch=nc();

    while(ch<'0'||ch>'9') ch=nc();

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=nc();

    return x;

}

char pbuf[100000],*pp=pbuf;

void push(const char ch) {

    if(pp-pbuf==100000) fwrite(pbuf,1,100000,stdout),pp=pbuf;

    *pp++=ch;

}

void write(ll x) {

    static int sta[50];

    int top=0;

    do{sta[top++]=x%10,x/=10;}while(x);

    while(top)push(sta[--top]+'0');

}

#define N 250050

ll f[N],g[N];

int head[N],to[N<<1],nxt[N<<1],val[N<<1],cnt,n,m;

int dep[N],fa[N],top[N],siz[N],son[N],dfn[N],a[N],h[N],la,S[N],tp,need[N],b[N<<1];

inline void add(int u,int v) {

    if(!v) return ;

    to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;

}

inline bool cmp(int x,int y) {return dfn[x]<dfn[y];}

void dfs1(int x) {

    int i; siz[x]=1; dfn[x]=++dfn[0];

    for(i=head[x];i;i=nxt[i]) {

        if(to[i]!=fa[x]) {

            fa[to[i]]=x; dep[to[i]]=dep[x]+1; g[to[i]]=min(g[x],1ll*val[i]);

            dfs1(to[i]);

            siz[x]+=siz[to[i]];

            if(siz[to[i]]>siz[son[x]]) son[x]=to[i];

        }

    }

}

void dfs2(int x,int t) {

    top[x]=t;

    if(son[x]) dfs2(son[x],t);

    int i;

    for(i=head[x];i;i=nxt[i]) {

        if(to[i]!=fa[x]&&to[i]!=son[x]) dfs2(to[i],to[i]);

    }

}

int lca(int x,int y) {

    while(top[x]!=top[y]) {

        if(dep[top[x]]>dep[top[y]]) swap(x,y);

        y=fa[top[y]];

    }

    return dep[x]<dep[y]?x:y;

}

void DP(int x) {

    if(need[x]) {f[x]=g[x]; return ;}

    ll sum=0;

    int i;

    for(i=head[x];i;i=nxt[i]) {

        DP(to[i]);

        sum+=f[to[i]];

    }

    f[x]=min(g[x],sum);

}

int main() {

    n=rd();

    g[1]=1ll<<60;

    int i,x,y,z;

    for(i=1;i<n;i++) {

        x=rd(); y=rd(); z=rd();

        add(x,y),val[cnt]=z;

        add(y,x),val[cnt]=z;

    }dep[1]=1;

    dfs1(1); dfs2(1,1); memset(head,0,sizeof(head)); cnt=0;

    m=rd();

    while(m--) {

        la=rd(); b[0]=la;

        for(i=1;i<=la;i++) a[i]=rd(),b[i]=a[i],need[a[i]]=1;

        sort(a+1,a+la+1,cmp);

        tp=0; S[++tp]=a[1];

        for(i=2;i<=la;i++) {

            int l=lca(a[i],S[tp]),c=0;

            while(tp&&dep[S[tp]]>dep[l]) {

                if(c) add(S[tp],c);

                c=S[tp--];

            }

            if(S[tp]==l&&c) add(S[tp],c);

            if(dep[S[tp]]<dep[l]&&c) add(l,c),S[++tp]=l;

            S[++tp]=a[i];

            b[++b[0]]=l;

        }

        while(tp>1) add(S[tp-1],S[tp]),tp--;

        // for(i=head[1];i;i=nxt[i]) printf("%d ",to[i]); puts("");

        // for(i=head[3];i;i=nxt[i]) printf("%d ",to[i]); puts("");

        // for(i=head[5];i;i=nxt[i]) printf("%d ",to[i]); puts("");

        // for(i=head[7];i;i=nxt[i]) printf("%d ",to[i]); puts("");

        // for(i=head[8];i;i=nxt[i]) printf("%d ",to[i]); puts("");

        DP(S[1]);

        write(f[S[1]]); push('\n');

        for(i=1;i<=b[0];i++) need[b[i]]=head[b[i]]=0;

        head[0]=0; cnt=0;

    }

    fwrite(pbuf,1,pp-pbuf,stdout);

}

/*

10

1 5 13

1 9 6

2 1 19

2 4 8

2 3 91

5 6 8

7 5 4

7 8 31

10 7 9

1

4 5 7 8 3

*/

相关文章