PLCT检查是什么C76【模板】动态DP P4719 动态 DP

// 动态DP+LCT O(nlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
#define notroot(x) lc(fa[x])==x||rc(fa[x])==x
const int N=100010,inf=(1<<30);
int n,m,a[N],f[N][2];
vector<int>G[N];
int ch[N][2],fa[N]; //splay:ch儿,fa父
struct matrix{
  int g[2][2];
  matrix(){g[0][0]=g[0][1]=g[1][0]=g[1][1]=-inf;}
  matrix operator*(matrix b){
    matrix t;
    for(int i=0;i<2;++i)
    for(int j=0;j<2;++j)
    for(int k=0;k<2;++k)
      t.g[i][j]=max(t.g[i][j],g[i][k]+b.g[k][j]);
    return t;
  }
}mt[N],tr[N]; //mt:节点x的g矩阵, tr:节点x的矩阵积

void dfs(int x)
  }
  mt[x].g[0][0]=mt[x].g[0][1]=f[x][0];
  mt[x].g[1][0]=f[x][1];
  tr[x]=mt[x]; //初始时每个点就是一个splay
}
void pushup(int x)
void rotate(int x)
void splay(int x)
}
void access(int x)
    if(y){    //y即将变成x的实儿子,减去其贡献
      mt[x].g[0][0]-=max(tr[y].g[0][0],tr[y].g[1][0]);
      mt[x].g[1][0]-=tr[y].g[0][0];
      mt[x].g[0][1]=mt[x].g[0][0];
    }
    rc(x)=y;   //把y变成x的右儿子(即x指向下面splay的根)
    pushup(x); //更新x
    x=fa[y=x]; //把x存于y,x继续爬到上面的splay
  }
}
void update(int x,int y){ //修改点权
  access(x); //通路
  splay(x);  //伸展
  mt[x].g[1][0]+=y-a[x]; //修改x点
  pushup(x); a[x]=y;
}
int main(){
  scanf("%d%d",&n,&m); int x,y;
  for(int i=1;i<=n;++i)scanf("%d",&a[i]);
  for(int i=1;i<n;i++){
    scanf("%d%d",&x,&y);
    G[x].push_back(y); G[y].push_back(x);
  }
  dfs(1); //预处理fa,f,mt,tr
  while(m--){
    scanf("%d%d",&x,&y);
    update(x,y);
    printf("%d
",max(tr[x].g[0][0],tr[x].g[1][0]));
  } 
}