P2495 [SDOI2011]消耗战 [树形dp, 虚树]

$[SDOI2011]消耗战$

题目描述见链接 .

---

$color{red}{正解部分}$

考虑单个询问如何处理, 有个很显然的 树形$dp$,
设 $Min\_p[k]$ 表示 $k$ 上方 最小的边, $F[k]$ 表示阻断 $k$ 以下所有 “含丰富能源” 的点 所需要的最小花费, 则

$F[k] = egin{cases} sum min(w_{k ightarrow to}, F[to]) k == 1\ min left( Min\_p[k],sum min(w_{k ightarrow to}, F[to]) ight) elseend{cases}$

单次询问复杂度是 $O(N)$ 的 .

注意到该题虽然有很多询问, 但是每次询问涉及的点数 $sum K le 500000$, 且上方 $dp$ 方程只与关键点有关 .
于是考虑将关于每次询问的 虚树 建立起来, 在 虚树 上进行 树形dp, 时间复杂度 $O(N+sum K)$ .

---

$color{red}{实现部分}$

注意到在建立 虚树 时, 点与点之间并不一定是直接相连的, 所以上方 $dp$ 方程中的 $w_{k ightarrow to}$ 无法方便地得知,

但是经过思考可以发现若使用 $Min\_p[to]$ 代替 $w_{k ightarrow to}$, 不会对答案造成影响 .

#include<bits/stdc++.h>

typedef long long ll;
const int maxn = 550005;
int N, M, K, Ans;
int num, dfnum, num1, cnt;
int head[maxn], Fa[maxn][21], stk[maxn], mark[maxn];
int A[maxn], dfn[maxn], dep[maxn], head1[maxn]; 
bool Bok[maxn], Used[maxn];
ll dp[maxn], Min_p[maxn];

struct Edge{ int nxt, to, dis; } edge[maxn<<1], ed[maxn<<1];

void Add(int from, int to, int dis){
        edge[num] = (Edge){ head[from], to, dis };
        head[from] = num ++;
}
void DFS_1(int k, int fa){
        dep[k] = dep[fa] + 1;
        dfn[k] = ++ dfnum;
        for(int i = 1; i <= 20; i ++) Fa[k][i] = Fa[Fa[k][i-1]][i-1];
        for(int i = head[k]; ~i; i = edge[i].nxt){
                int to = edge[i].to;
                if(dep[to]) continue ;
                Fa[to][0] = k;
                if(k != 1) Min_p[to] = std::min(Min_p[k], 1ll*edge[i].dis);
                else Min_p[to] = edge[i].dis;
                DFS_1(to, k);
        }
}
int LCA(int x, int y){
        if(dep[x] < dep[y]) std::swap(x, y);
        for(int i = 20; i >= 0; i --)
                if(dep[Fa[x][i]] >= dep[y]) x = Fa[x][i];
        if(x == y) return x; 
        for(int i = 20; i >= 0; i --) 
                if(Fa[x][i] != Fa[y][i]) x = Fa[x][i], y = Fa[y][i];
        return Fa[x][0];
}
bool cmp_1(int a, int b){ return dfn[a] < dfn[b]; }

void Add_2(int from, int to){
        ed[num1] = (Edge){ head1[from], to, 0 };
        head1[from] = num1 ++;
}
void Build(){
        num1 = 0; std::sort(A+1, A+K+1, cmp_1);
        int top = 0; stk[++ top] = 1;
        for(int i = 1; i <= K; i ++){
                int u = stk[top], v = A[i];
                int p = LCA(u, v);
                if(!Used[p]) Used[p] = 1, mark[++ cnt] = p;
                if(p == u) stk[++ top] = v;
                else{
                        while(dep[stk[top-1]] >= dep[p] && top >= 2)
                                Add_2(stk[top-1], stk[top]), Add_2(stk[top], stk[top-1]), top --;
                        if(stk[top] != p) Add_2(p, stk[top]), Add_2(stk[top], p), stk[top] = p; 
                        stk[++ top] = v;
                }
        }
        for(int i = 1; i <= top; i ++) 
                if(i != top) Add_2(stk[i], stk[i+1]), Add_2(stk[i+1], stk[i]);
}
void Dp(int k, int la){
        dp[k] = Min_p[k]; ll tmp = 0;
        for(int i = head1[k]; ~i; i = ed[i].nxt){
                int to = ed[i].to;
                if(to == la) continue ;
                Dp(to, k);
                tmp += std::min(dp[to], 1LL*Min_p[to]);
        }
        if(!Bok[k]) dp[k] = std::min(dp[k], tmp);
}

void Solve(){
        DFS_1(1, 0);
        scanf("%d", &M);
        while(M --){
                scanf("%d", &K);
                for(int i = 1; i <= K; i ++) scanf("%d", &A[i]), Bok[A[i]] = Used[A[i]] = 1, mark[++ cnt] = A[i];
                Build(); Min_p[1] = 0x3f3f3f3f3f3f3f3f; Dp(1, 0);
                printf("%lld
", dp[1]);
                for(int i = 1; i <= cnt; i ++) head1[mark[i]] = -1, Used[mark[i]] = Bok[mark[i]] = 0;
                cnt = 0;
        }
}

void Input_1(){
        memset(head, -1, sizeof head); memset(head1, -1, sizeof head1);
        scanf("%d", &N);
        int u, v, w;
        for(int i = 1; i < N; i ++) scanf("%d%d%d", &u, &v, &w), Add(u, v, w), Add(v, u, w);
}

int main(){
        Input_1(); Solve();
        return 0;
}