题目：https://www.luogu.org/problemnew/show/P4719
关于动态DP似乎有猫锟的WC2018论文，但找不见；还是算了。
http://immortalco.blog.uoj.ac/archive
动态DP大概就是求这样的问题。
把轻儿子对自己的转移值写进矩阵 g 里，重新定义一下乘法运算，自己的值矩阵 f 就是重儿子的 f 乘上自己的 g 了。
树剖的线段树维护区间内的那些 g 的连乘积，则从自己开始到自己所在重链的底端这一段的 g 连乘就是自己的 f 了（因为底端是叶子，所以本来该乘一个 f ，就和不乘一样了）。
修改的时候就是改一些 g 。自己如果在 x 的轻儿子里，则需要改一下 x 的 g 。一次会改 log 个 g 。
求答案就是 1 所在重链的连乘积。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ls Ls[cr]
#define rs Rs[cr]
using namespace std;
const int N=1e5+,INF=1e9+;
int n,m,w[N],hd[N],xnt,to[N<<],nxt[N<<],tot,Ls[N<<],Rs[N<<];
int dfn[N],siz[N],son[N],rnk[N],dep[N],fa[N],top[N],bj[N],dp[N][];
int Mx(int a,int b){return a>b?a:b;}
struct Matrix{
int a[][];
Matrix(){a[][]=a[][]=a[][]=a[][]=-INF;}
Matrix operator+ (const Matrix &b)const
{
Matrix c;
for(int i=;i<=;i++)
for(int k=;k<=;k++)
for(int j=;j<=;j++)
c.a[i][j]=Mx(c.a[i][j],a[i][k]+b.a[k][j]);
return c;
}
}g[N],t[N<<];
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();
return fx?ret:-ret;
}
void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}
void dfs(int cr)
{
dep[cr]=dep[fa[cr]]+; siz[cr]=;
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=fa[cr])
{
fa[v]=cr; dfs(v);
siz[cr]+=siz[v];
siz[v]>siz[son[cr]]?son[cr]=v:;
}
}
void dfsx(int cr)
{
dfn[cr]=++tot; rnk[tot]=cr;
dp[cr][]=; dp[cr][]=w[cr];
if(son[cr])
{
top[son[cr]]=top[cr];dfsx(son[cr]);
dp[cr][]+=Mx(dp[son[cr]][],dp[son[cr]][]);
dp[cr][]+=dp[son[cr]][];
}
g[cr].a[][]=g[cr].a[][]=;
g[cr].a[][]=w[cr]; g[cr].a[][]=-INF;
if(!son[cr]){ bj[top[cr]]=tot; return;}
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=fa[cr]&&v!=son[cr])
{
top[v]=v; dfsx(v);
dp[cr][]+=Mx(dp[v][],dp[v][]); dp[cr][]+=dp[v][];
g[cr].a[][]+=Mx(dp[v][],dp[v][]); g[cr].a[][]=g[cr].a[][];
g[cr].a[][]+=dp[v][];
}
}
void build(int l,int r,int cr)
{
if(l==r){t[cr]=g[rnk[l]];return;}
int mid=l+r>>;
ls=++tot; build(l,mid,ls);
rs=++tot; build(mid+,r,rs);
t[cr]=t[ls]+t[rs];
}
void updt(int l,int r,int cr,int p)
{
if(l==r){t[cr]=g[rnk[l]];return;}
int mid=l+r>>;
if(p<=mid)updt(l,mid,ls,p);
else updt(mid+,r,rs,p);
t[cr]=t[ls]+t[rs];
}
Matrix query(int l,int r,int cr,int L,int R)
{
if(l>=L&&r<=R)return t[cr];
int mid=l+r>>;
if(R<=mid)return query(l,mid,ls,L,R);
if(mid<L) return query(mid+,r,rs,L,R);
return query(l,mid,ls,L,R)+query(mid+,r,rs,L,R);
}
Matrix calc(int cr){ return query(,n,,dfn[cr],bj[cr]);}
void cz(int x,int y)
{
g[x].a[][]+=y-w[x]; w[x]=y;
Matrix k1=calc(top[x]); updt(,n,,dfn[x]); Matrix k2=calc(top[x]);
while(fa[top[x]])
{
int d=fa[top[x]];
g[d].a[][]+=Mx(k2.a[][],k2.a[][])-Mx(k1.a[][],k1.a[][]);
g[d].a[][]=g[d].a[][];
g[d].a[][]+=k2.a[][]-k1.a[][];
x=d;
k1=calc(top[x]); updt(,n,,dfn[x]); k2=calc(top[x]);
}
}
int main()
{
n=rdn();m=rdn();
for(int i=;i<=n;i++)w[i]=rdn();
for(int i=,u,v;i<n;i++)
{
u=rdn(); v=rdn(); add(u,v); add(v,u);
}
dfs(); top[]=; dfsx(); tot=; build(,n,);//tot=1!!!!!!
for(int i=,x,y;i<=m;i++)
{
x=rdn(); y=rdn(); cz(x,y);
Matrix d=calc();
printf("%d\n",Mx(d.a[][],d.a[][]));
}
return ;
}