luogu4719是模板题了 看了RabitHu的题解
简言之
树链剖分 建一颗线段树维护该段[l,r]的部分答案([l,r]这段不一定联通) 部分答案：不包括重儿子的答案 这样就勉强维护了复杂度
矩阵乘法只是把转移方程写成矩阵的形式 无脑又好写 //Ctrl+V毫无压力
#include <cstdio> #include <cstring> #include <iostream> using namespace std; typedef long long ll; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } template <class T>inline void read(T &x){ char c=nc();x=0;int f=1; for(;!isdigit(c);c=nc())if(c=='-')f=-1; for(;isdigit(c);c=nc())x=(x<<1)+(x<<3)+c-'0'; x*=f; } template <class T>inline void write(T x){ if(x<0)putchar('-'),x=-x; if(x>=10)write(x/10); putchar('0'+x); } const int N=100002; int n,m,a[N],cnt,head[N],nex[N<<1],to[N<<1]; int fa[N],son[N],siz[N],top[N],idx[N],pos[N],tot,ed[N]; ll f[N][2]; struct matrix{ ll g[2][2]; matrix(){memset(g, 0, sizeof(g));} matrix operator*(const matrix &b)const{ matrix c; for(int i=0;i<2;++i) for(int j=0;j<2;++j) for(int k=0;k<2;++k) c.g[i][j]=max(c.g[i][j],g[i][k]+b.g[k][j]); return c; } }val[N],data[N<<2]; inline void add(int u, int v){ nex[++cnt]=head[u],head[u]=cnt,to[cnt]=v; } inline void init(){ static int q[N]; q[1]=1; for(int ql=1,qr=1;ql<=qr;++ql) for(int u=q[ql],e=head[u],v;e;e=nex[e]) if((v=to[e])!=fa[u])fa[v]=u,q[++qr]=v; for(int qr=n,u;qr;--qr){ ++siz[u=q[qr]],siz[fa[u]]+=siz[u]; if(siz[u]>siz[son[fa[u]]])son[fa[u]]=u; } for(int ql=1,u;ql<=n;++ql) if(!top[u=q[ql]]){ for(int v=u;v;v=son[v]) top[v]=u,idx[pos[v]=++tot]=v; ed[u]=tot; } for(int qr=n,u;qr;--qr){ u=q[qr],f[u][1]=max(0,a[u]); for(int e=head[u],v;e;e=nex[e]) if((v=to[e])!=fa[u]) f[u][0]+=max(f[v][0],f[v][1]),f[u][1]+=f[v][0]; } } inline void build(int k,int l,int r){ if(l==r){ ll g0=0,g1=a[idx[l]]; for(int u=idx[l],e=head[u],v;e;e=nex[e]) if((v=to[e])!=fa[u]&&v!=son[u]) g0+=max(f[v][0],f[v][1]),g1+=f[v][0]; data[k].g[0][0]=data[k].g[0][1]=g0; data[k].g[1][0]=g1,val[l]=data[k]; return; } int mid=(l+r)>>1; build(k<<1,l,mid),build(k<<1|1,mid+1,r); data[k]=data[k<<1]*data[k<<1|1]; } void change(int k,int l,int r,int p){ if(l==r){data[k] = val[l];return;} int mid=(l+r)>>1; if(p<=mid)change(k<<1,l,mid,p);else change(k<<1|1,mid+1,r,p); data[k]=data[k<<1]*data[k<<1|1]; } matrix query(int k,int l,int r,int ql,int qr){ if(ql<=l&&qr>=r)return data[k]; int mid=(l+r)>>1; if(qr<=mid)return query(k<<1,l,mid,ql,qr); if(ql>mid)return query(k<<1|1,mid+1,r,ql,qr); return query(k<<1,l,mid,ql,qr)*query(k<<1|1,mid+1,r,ql,qr); } matrix ask(int u){ return query(1,1,n,pos[top[u]],ed[top[u]]); } inline void path_change(int u,int x){ val[pos[u]].g[1][0]+=x-a[u],a[u]=x; matrix od,nw; while(u){ od=ask(top[u]); change(1,1,n,pos[u]); nw=ask(top[u]); u=fa[top[u]]; val[pos[u]].g[0][0]+=max(nw.g[0][0],nw.g[1][0])-max(od.g[0][0],od.g[1][0]); val[pos[u]].g[0][1]=val[pos[u]].g[0][0]; val[pos[u]].g[1][0]+=nw.g[0][0]-od.g[0][0]; } } int main(){ read(n),read(m); for(int i=1;i<=n;++i)read(a[i]); for(int i=1,u,v;i<n;++i)read(u),read(v),add(u,v),add(v,u); init(),build(1,1,n); int u,x;matrix t; while(m--){ read(u),read(x); path_change(u,x); t=ask(1); write(max(t.g[0][0], t.g[1][0])),puts(""); } return 0; }转载于:https://www.cnblogs.com/MikuKnight/p/10046553.html
