Luogu | P2495 [SDOI 2011] 消耗战 | 动态规划 | 虚树 / DFS 序 / 树规

---

Description

在一场战争中，战场由 $n$ 个岛屿和 $n-1$ 个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为 $1$ 的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他 $k$ 个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。

侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到 $1$ 号岛屿上）。不过侦查部门还发现了这台机器只能够使用 $m$ 次，所以我们只需要把每次任务完成即可。

---

Input Format

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

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

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

接下来 $m$ 行，每行一个整数 $k_i$，代表第 $i$ 次后，有 $k_i$ 个岛屿资源丰富，接下来 $k$ 个整数 $h_1,h_2,…h_k$，表示资源丰富岛屿的编号。

---

Output Format

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

---

Input Sample

Sample 01

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

---

Output Sample

Sample 01

12
32
22

---

Data Range

$n \le 25 \times 10^4$，$\sum k_i \le 5 \times 10^5$，$c_i \le 10^5$。

---

Solution

树上动态规划：设 $F[i]$ 为将以 $i$ 为根的子树中所有结点全部切断所需的最小值。$F[i] = \sum\min{ F[j] , minl[j]}$，其中 $minl[j]$ 代表从根结点到 $j$ 所经过的边权最小值。

考虑将每个询问的结点按照 DFS 序排序，则与这个询问有关的所有的结点只是在当前的所有结点的基础上加上每两个相邻结点的 LCA。

这样对于每个询问就建立了一颗基于 DFS 序的虚树。考虑模拟 DFS 的过程，每个点在 $in$ 入栈， $out$ 出栈，dp 即可。

---

Code

#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

using std::min;
using std::sort;
using std::stack;

typedef long long ll;

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

struct edge{
    int from;
    int to;
    int next;
    int w;
}e[500005];

struct pt{
    int dfn;
    int fa_dfn;
};

int N;
int M;
int cnt;
int fcnt;
int node;
int stamp;

int first[250005];
int last[250005];
int in[250005];
int out[250005];
int src[250005];
int dfn_src[250005];
int in_ori[250005];
int size[250005];
int fa[250005];
int dep[250005];
int hvs[250005];
int top[250005];
int fin_tr[250005];
int dfn_fin[250005];

ll F[250005];
ll minn[250005];

bool exist[250005];

stack<pt>stk;

void addedge(int u,int v,int w){
    e[++node]=(edge){u,v,0,w};
    if(first[u]==0) first[u]=node;
    else e[last[u]].next=node;
    last[u]=node; return;
}

void DFS(int x){
    in[x]=++stamp;
    in_ori[stamp]=x;
    for(int p=first[x];p;p=e[p].next){
        int y=e[p].to;
        if(in[y])
            continue;
        minn[y]=min(minn[x],(ll)e[p].w);
        DFS(y);
    }
    out[x]=stamp;
}

void DFS1(int x){
    size[x]=1;
    dep[x]=dep[fa[x]]+1;
    for(int p=first[x];p;p=e[p].next){
        int y=e[p].to;
        if(y==fa[x])
            continue;
        fa[y]=x;
        DFS1(y);
        size[x]+=size[y];
        if(size[y]>size[hvs[x]])
            hvs[x]=y;
    }
    return;
}

void DFS2(int x,int head){
    top[x]=head;
    if(hvs[x])
        DFS2(hvs[x],head);
    else
        return;
    for(int p=first[x];p;p=e[p].next){
        int y=e[p].to;
        if(y==fa[x]||y==hvs[x])
            continue;
        DFS2(y,y);
    }
    return;
}

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

int main(){
    int f,t,w;
    Read(N);
    rep(i,2,N){
        Read(f);
        Read(t);
        Read(w);
        addedge(f,t,w);
        addedge(t,f,w);
    }
    minn[1]=0x7f7f7f7f7f7f7f7f;
    DFS(1);
    DFS1(1);
    DFS2(1,1);
    Read(M);
    rep(i,1,M){
        fcnt=0;
        Read(cnt);
        rep(j,1,cnt)
            Read(src[j]);
        rep(j,1,cnt)
            dfn_src[j]=in[src[j]];
        sort(dfn_src+1,dfn_src+1+cnt);
        rep(j,1,cnt){
            if(!exist[in_ori[dfn_src[j]]]){
                exist[in_ori[dfn_src[j]]]=1;
                fin_tr[++fcnt]=in_ori[dfn_src[j]];
                F[dfn_src[j]]=minn[fin_tr[fcnt]];
            }
        }
        rep(j,1,cnt-1){
            int lca=LCA(in_ori[dfn_src[j]],in_ori[dfn_src[j+1]]);
            if(!exist[lca]){
                exist[lca]=1;
                fin_tr[++fcnt]=lca;
            }
        }
        rep(j,1,fcnt)
            dfn_fin[j]=in[fin_tr[j]];
        sort(dfn_fin+1,dfn_fin+1+fcnt);
        rep(j,1,fcnt){
            while(!stk.empty() && out[in_ori[stk.top().dfn]]<dfn_fin[j]){
                pt x=stk.top();
                stk.pop(); 
                F[x.fa_dfn]+=min(F[x.dfn],(ll)minn[in_ori[x.dfn]]);
            }// 弹栈，直到栈顶结点是当前点的祖先
            if(!stk.empty())
                stk.push((pt){dfn_fin[j],stk.top().dfn});
            else
                stk.push((pt){dfn_fin[j],0});
        }
        while(!stk.empty()){
            pt x=stk.top();
            stk.pop(); 
            F[x.fa_dfn]+=min(F[x.dfn],(ll)minn[in_ori[x.dfn]]);
        }
        printf("%lld\n",F[0]);
        rep(j,1,fcnt)
            F[dfn_fin[j]]=0;
        F[0]=0;
        rep(j,1,cnt)
            exist[in_ori[dfn_src[j]]]=0;
        rep(j,1,cnt-1){
            int lca=LCA(in_ori[dfn_src[j]],in_ori[dfn_src[j+1]]);
            exist[lca]=0;
        }
    }
    return 0;
}