洪水_牛客博客

题目：

给你一棵树，节点从 $1$ 到 $n$ 编号，每个节点有一个权值，有若干次操作，操作有以下两种：

$(C,x,delta)$ ：将编号为 $x$ 的点的权值改为 $delta$

$(Q,x)$ :询问将 $x$ 号节点为根的子树中的所有叶子结点与子树外的其他所有叶子节点分离的最小代价，分离可以通过删除节点实现，删除一个节点的对应代价为该点的权值

数据范围： $n<=200000$ ，任意 $delta$ 均为非负数，答案在 $long long$ 范围内

题解：

这题是经典的动态DP。

这种题往往是没修改时是普通的DP，然后加上修改操作，就要用树剖或LCT进行维护。

维护也有两种形式，一种纯粹是维护一个DP方程，一种是把DP方程转换为一个新定义矩阵然后像矩乘一样转移。

我还是用树剖维护一个DP方程，我觉得这样好理解。

第一步（写出普通DP）：

我们写出普通的DP， $f[u]表示把子树u的叶子节点全部不和u相连的最小代价$ 。

$f[u]=min(val[u],\sum_{}f[v])$

答案就是 $f[u]$

第二步（写出动态DP） :

当这个DP在序列上进行时，我们比较容易使用线段树维护序列动态DP。

当这个DP在树上进行时，考虑将这棵树轻重链剖分，转化为序列问题。

根据套路:设 $g[u]=\sum_{}f[v] (v是u的轻儿子)$

那么: $f[u]=min(val[u],g[u]+f[son[u]])$

第三步（考虑如何维护） ：

因为是重链，看成一条直线， $f[i]=max(val[i],f[i-1]+g[i])$

这不就是求最大子段和吗。

最大子段和可以用线段树快速维护。

对于重链，我们直接线段树，对于轻链，我们就暴力转移即可（因为每次轻链只有一条）

线段树记录什么值呢？

使用线段树维护最小前缀和（在重链这一段区间的某位置选出一个点使得总代价 **前面的 $g$ +当前的 $v$ 最小）及总和（这段区间都不选，所有的 $g$ 之和**)

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid (l+r)/2
const int N=1e6+5;
int n,m,t,T,v[N],g[N],f[N],head[N],size[N],son[N],pos[N],end[N],top[N],fa[N];
struct E{
    int too,next;
}edge[N*2];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
struct node{
    int sum,ls;
}w[N],tree[N*4];
node operator + (node a,node b)
{
    return (node){a.sum+b.sum,min(a.ls,a.sum+b.ls)};
}
void add(int a,int b)
{
    edge[++T].too=b;edge[T].next=head[a];head[a]=T;
}
void dfs(int u,int fat)
{
    size[u]=1;fa[u]=fat;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].too;
        if(v==fat)continue;
        dfs(v,u);
        size[u]+=size[v];
        if(size[v]>size[son[u]])son[u]=v;
    }
}
void dfs2(int u,int tp)
{
    top[u]=tp;pos[u]=++t;end[u]=u;f[u]=v[u];
    if(son[u])
    {
        dfs2(son[u],tp);end[u]=end[son[u]];
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].too;
            if(v==fa[u]||v==son[u])continue;
            dfs2(v,v);
            g[u]+=f[v];
        }
        f[u]=min(f[u],f[son[u]]+g[u]);
    }
    w[pos[u]]=(node){g[u],v[u]};
}
void build(int nod,int l,int r)
{
    if(l==r)
    {
        tree[nod]=w[l];
        return;
    }
    build(nod*2,l,mid);
    build(nod*2+1,mid+1,r);
    tree[nod]=tree[nod*2]+tree[nod*2+1];
}
void updatev(int nod,int l,int r,int x,int v)
{
    if(l==r)
    {
        tree[nod].ls+=v;
        return;
    }
    if(x<=mid)updatev(nod*2,l,mid,x,v);
    else updatev(nod*2+1,mid+1,r,x,v);
    tree[nod]=tree[nod*2]+tree[nod*2+1];
}
void updateg(int nod,int l,int r,int x,int v)
{
    if(l==r)
    {
        tree[nod].sum+=v;
        return;
    }
    if(x<=mid)updateg(nod*2,l,mid,x,v);
    else updateg(nod*2+1,mid+1,r,x,v);
    tree[nod]=tree[nod*2]+tree[nod*2+1];
}
node query(int nod,int l,int r,int L,int R)
{
    if(L==l&&r==R)return tree[nod];
    if(R<=mid)return query(nod*2,l,mid,L,R);
    else if(L>mid)return query(nod*2+1,mid+1,r,L,R);
    else return query(nod*2,l,mid,L,mid)+query(nod*2+1,mid+1,r,mid+1,R);
}
void change(int x,int v)
{
    int y=x;
    int t;
    while(x)
    {
        t=query(1,1,n,pos[top[x]],pos[end[x]]).ls;
        if(x==y)updatev(1,1,n,pos[x],v);
        else{updateg(1,1,n,pos[x],v);}
        v=query(1,1,n,pos[top[x]],pos[end[x]]).ls-t;
        x=fa[top[x]];
    }
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)v[i]=read();
    for(int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add(x,y);
        add(y,x);
    }
    dfs(1,0);dfs2(1,1);
    build(1,1,n);
    m=read();
    char s[35];
    while(m--)
    {
        scanf("%s",s);
        int x=read();
        if(s[0]=='C')
        {
            int y=read();
            change(x,y);
        }
        else printf("%lld\n",query(1,1,n,pos[x],pos[end[x]]).ls);
    }
    return 0;
}