4719 【模板】"动态 DP"&动态树分治 题解

· · 题解

暴力竟然进了第一页！！！

还是一道紫题！！！

我也没懂，我这O(mh)的算法竟然能过！！！

思路：

$dp[i][1]$记录选此点的最大值 先树形$dp$(树形$dp$应该都会吧，都来做紫题了)，然后对于每个修改都重新树形$dp$，但是只需要修改他的祖先。~~如果出题毒瘤，那就会变成~~$O(nm)

重新计算他的祖先时，不用把每个儿子都算一遍，只需要算这个点有修改过的儿子前后两次的差值。

code time：

 /*      西江月·证明
    即得易见平凡，仿照上例显然。
   留作习题答案略， 读者自证不难。 

    反之亦然同理，推论自然成立。 
    略去过程QED，由上可知证毕。*/
#include<set>
#include<map>
#define mod 10
#include<list>
#include<cmath>
#include<queue>
#include<ctime>
#include<stack>
#include<ctime>
#include<bitset>
#include<memory>
#include<cstdio>
#include<string>
#include<sstream>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rg register
#define bll __int128 
#define ll long long
#define inf 214232409
#define ull unsigned long long
#define debug() cout<<"SOSOSOSOSOSOSOS!!!!!!!!!"
#define C(i,j) dp[i+1][j+1]
using namespace std;
int read(){
    int ans=0,f=1;char a=getchar();while(a>'9'||a<'0'){if(a=='-')f=(-1);a=getchar();}
    while(a>='0'&&a<='9')ans=(ans<<3)+(ans<<1)+a-'0',a=getchar();return ans*f;
}//一条long long的黄金分割线---------------------------------------------------------------------------------------------
int n,m,v[100005],first[100005],cnt,fa[100005],root=1,dp[100005][2],x,y,z,now,now_val;
struct edge{
    int to,nxt;
}e[200005];
void add(int x,int y){
    e[++cnt].nxt=first[x];
    e[cnt].to=y;
    first[x]=cnt;
}
void dfs(int now,int f){
    fa[now]=f;dp[now][1]=v[now];
    for(int i=first[now],v;i;i=e[i].nxt){
        v=e[i].to;
        if(v==f)continue;
        dfs(v,now);
        dp[now][0]+=max(dp[v][0],dp[v][1]);
        dp[now][1]+=dp[v][0];
    }
}//树形dp ，不会可以先去学习一下。 
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)v[i]=read();
    for(int i=1;i<n;i++)add(read(),read());
    dfs(root,-1);
    for(int i=1;i<=m;i++){
        x=read();y=read();
        int fx=dp[x][0],fy=dp[x][1];
        dp[x][1]=dp[x][1]-v[x]+y;
        int now=fa[x],son=x,ldp0=fx,ldp1=fy;
        while(now+1){
            int fx=dp[now][0],fy=dp[now][1];
            dp[now][0]-=max(ldp0,ldp1)-max(dp[son][0],dp[son][1]);//根据上面dfs的树形dp递推公式统计差值 
            dp[now][1]-=ldp0-dp[son][0];//同理
            son=now,now=fa[now],ldp0=fx,ldp1=fy;//记录当前点，因为无法知道下一个点的儿子，记录当下一个点
            //还记录原来dp的值，计算差值 
        }
        v[x]=y;
        printf("%d\n",max(dp[root][0],dp[root][1]));//输出dp结果 
    }
    return 0;
}
/*
 * ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
 * │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  ┌┐    ┌┐    ┌┐
 * └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └┘    └┘    └┘
 * ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
 * │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
 * ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
 * │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
 * ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
 * │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter  │               │ 4 │ 5 │ 6 │   │
 * ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
 * │ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
 * ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
 * │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
 * └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
 */