题解 P2495 【[SDOI2011]消耗战】

· · 题解

虚树的题为什么要用虚树做？

假如只有一次询问，考虑如何 dp 。

设 f_u 表示将子树 u 内的所有关键点到 u 的路径切断的最小代价，那么转移为 f_u=\sum_{v}\min(f_v,w(u,v))，即选择是否断掉儿子 v 到 u 的这条边。特别的，如果 u 本身是关键点，那么 f_u=\inf ，因为不可能通过断边消除 u\rightarrow u 的这条路径。

以 1 为根开始做的话，答案就是f_1。

可以发现，这个 dp 的过程非常简洁，由几个简单的操作组成：求和，取 \min。

这两个操作都可以在线段树上进行维护，让线段树上第 i 个叶子表示第 i 次询问的 dp 值，那么取 \min 就是全局取 \min，求和就是线段树合并的时候对应位置相加。

那么写一个线段树合并就可以通过这道题了，复杂度为O(n+mlogm)，跑起来比想象中慢，但是思维量和代码量都比虚树少上不少。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define lc t[p].ls
#define rc t[p].rs
#define I inline int
#define V inline void
#define lson lc,L,mid
#define rson rc,mid+1,R
#define ll long long int
#define root(x) rt[x],1,m
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(u,e) for(int i=e##h[u],v;v=e[i].t,i;i=e[i].n)
#define add(x,y,w,e) e[++tot]=(edge){y,e##h[x],w},e##h[x]=tot
const int N=5e5+1;
int n,m,tot,eh[N],qh[N],rt[N];
struct edge{int t,n,w;}e[N],q[N];
struct ele{
    int ls,rs;ll v;
    V upd(ll x){if(v>x)v=x;}
}t[N<<5];
V input(){
    scanf("%d",&n);int x,y,w;
    FOR(i,2,n)scanf("%d%d%d",&x,&y,&w),add(x,y,w,e),add(y,x,w,e);
    scanf("%d",&m),tot=w=0;
    FOR(i,1,m)for(scanf("%d",&n);n--;)scanf("%d",&x),add(x,i,w,q);
}
V ins(int&p,int L,int R,int x){
    if(x<L||x>R)return;
    if(!p)t[p=++tot].v=1ll<<40;
    if(L==R)return;int mid=L+R>>1;
    ins(lson,x),ins(rson,x);
}
V solve(int p){t[lc].upd(t[p].v),t[rc].upd(t[p].v),t[p].v=1ll<<40;}
I merge(int x,int y){
    if(!x||!y)return x|y;
    if(!t[x].ls&&!t[x].rs)return t[x].v+=t[y].v,x;
    solve(x),solve(y);
    t[x].ls=merge(t[x].ls,t[y].ls);
    t[x].rs=merge(t[x].rs,t[y].rs);
    return x;
}
V dfs(int u,int fa){
    REP(u,q)ins(rt[u],1,m,v);
    REP(u,e)if(v^fa)
        dfs(v,u),t[rt[v]].upd(e[i].w),rt[u]=merge(rt[u],rt[v]);
}
V output(int p,int L,int R){
    if(L==R)return void(cout<<t[p].v<<'\n');
    int mid=L+R>>1;solve(p),output(lson),output(rson);
}
V work(){tot=0,dfs(1,0),output(rt[1],1,m);}
int main(){
    input();
    work();
    return 0;
}