bzoj 4712: 洪水 樹鍊剖分+線段樹優化dp

題意

小A走到一個山腳下，準備給自己造一個小屋。這時候，小A的朋友（op，又叫管理者）打開了創造模式，然後飛到山頂放了格水。于是小A面前出現了一個瀑布。作為平民的小A隻好老實巴交地爬山堵水。那麼問題來了：我們把這個瀑布看成是一個n個節點的樹，每個節點有權值（爬上去的代價）。小A要選擇一些節點，以其權值和作為代價将這些點删除（堵上），使得根節點與所有葉子結點不連通。問最小代價。不過到這還沒結束。小A的朋友覺得這樣子太便宜小A了，于是他還會不斷地修改地形，使得某個節點的權值發生變化。不過到這還沒結束。小A覺得朋友做得太絕了，于是放棄了分離所有葉子節點的方案。取而代之的是，每次他隻要在某個子樹中（和子樹之外的點完全無關）。于是他找到你。

n<=200000，保證任意增加的權值都為非負數。

分析

如果沒有修改操作的話，設dp[x]表示以x為根的答案， h[x]=∑dp[son] ，顯然有dp[x]=min(w[x],h[x])

在 w[x] 增加一個值後，dp[x]肯定不會減少。設dp[x]增加了delta，那麼如果x的父親f滿足h[f]+delta不大于w[f]，那麼dp[f]就要加上delta。同理可以拓展到f的父親。

那麼我們可以用線段樹記錄每個點w[x]-h[x]的最小值，然後線上段樹上二分找到深度最小的一個點x滿足w[x]-h[x]不小于delta，然後将這些點的dp值減去delta即可。

對于x的父親，它的dp值需要重新計算。而如果它的dp值改變了，我們就重複上述過程即可。

因為每個點的dp值重新計算後其h值就會大于其w值，也就是說重計算最多隻有n+m次，是以總複雜度是O((n+m)log^2)。

更具體的細節可以去看Claris的部落格。

代碼

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N=;
const LL inf=(LL)<<;

int n,m,cnt,last[N],fa[N],dep[N],top[N],size[N],dfn[N],tim,bel[N];
LL h[N],dp[N],w[N];
struct edge{int to,next;}e[N*2];
struct tree{LL tag,mn;}t[N*4];

void addedge(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
    e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}

void dfs1(int x)
{
    dep[x]=dep[fa[x]]+;size[x]=;
    for (int i=last[x];i;i=e[i].next)
    {
        if (e[i].to==fa[x]) continue;
        fa[e[i].to]=x;
        dfs1(e[i].to);
        size[x]+=size[e[i].to];
        h[x]+=dp[e[i].to];
    }
    if (size[x]==) h[x]=inf;
    dp[x]=min(w[x],h[x]);
}

void dfs2(int x,int chain)
{
    dfn[x]=++tim;bel[tim]=x;top[x]=chain;int k=;
    for (int i=last[x];i;i=e[i].next)
        if (e[i].to!=fa[x]&&size[e[i].to]>size[k]) k=e[i].to;
    if (!k) return;
    dfs2(k,chain);
    for (int i=last[x];i;i=e[i].next)
        if (e[i].to!=fa[x]&&e[i].to!=k) dfs2(e[i].to,e[i].to);
}

void pushdown(int d)
{
    if (!t[d].tag) return;
    LL w=t[d].tag;t[d].tag=;
    t[d*2].tag+=w;t[d*2+].tag+=w;
    t[d*2].mn-=w;t[d*2+].mn-=w;
}

void updata(int d)
{
    t[d].mn=min(t[d*2].mn,t[d*2+].mn);
}

void build(int d,int l,int r)
{
    if (l==r) {int x=bel[l];t[d].tag=h[x];t[d].mn=w[x]-h[x];return;}
    int mid=(l+r)/;
    build(d*2,l,mid);build(d*2+,mid+,r);
    updata(d);
}

LL get_h(int d,int l,int r,int x)
{
    if (l<r) pushdown(d);
    if (l==r) {t[d].mn=w[bel[l]]-t[d].tag;return t[d].tag;}
    int mid=(l+r)/;LL ans;
    if (x<=mid) ans=get_h(d*2,l,mid,x);
    else ans=get_h(d*2+,mid+,r,x);
    updata(d);return ans;
}

int modify(int d,int l,int r,int x,int y,LL delta)
{
    if (l<r) pushdown(d);
    int mid=(l+r)/,ans;
    if (l==x&&r==y)
    {
        if (t[d].mn>=delta) {t[d].tag+=delta;t[d].mn-=delta;return ;}
        if (l==r) {t[d].tag+=delta;t[d].mn-=delta;return bel[l];};
        int z=modify(d*2+,mid+,r,mid+,y,delta);
        if (z) {updata(d);return z;}
        ans=modify(d*2,l,mid,x,mid,delta);
        updata(d);return ans;
    }
    if (y<=mid) ans=modify(d*2,l,mid,x,y,delta);
    else if (x>mid) ans=modify(d*2+,mid+,r,x,y,delta);
    else
    {
        int z=modify(d*2+,mid+,r,mid+,y,delta);
        if (z) ans=z;
        else ans=modify(d*2,l,mid,x,mid,delta);
    }
    updata(d);
    return ans;
}

void modify(int x,LL delta)
{
    if (delta<=) return;
    int z=;
    while (x)
    {
        z=modify(,,n,dfn[top[x]],dfn[x],delta);
        if (z) break;
        x=fa[top[x]];
    }
    if (z) modify(fa[z],w[z]-get_h(,,n,dfn[z])+delta);
}

int main()
{
    scanf("%d",&n);
    for (int i=;i<=n;i++) scanf("%lld",&w[i]);
    for (int i=;i<n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        addedge(x,y);
    }
    dfs1();dfs2(,);
    build(,,n);
    scanf("%d",&m);
    while (m--)
    {
        char ch[];scanf("%s",ch);
        if (ch[]=='Q')
        {
            int x;scanf("%d",&x);
            printf("%lld\n",min(get_h(,,n,dfn[x]),w[x]));
        }
        else
        {
            int x;LL y;scanf("%d%lld",&x,&y);
            w[x]+=y;LL h=get_h(,,n,dfn[x]);
            if (w[x]-y<h) modify(fa[x],min(h,w[x])-min(h,w[x]-y));
        }
    }
    return ;
}