Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

#define INF 0x3f3f3f3f

struct matrix

{

	ll m[2][2];

	matrix(){memset(m,0,sizeof(m));}

	friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

		for(int i = 0;i <= 1;++i)

			for(int j = 0;j <= 1;++j)

				for(int k = 0;k <= 1;++k)

					c.m[i][j] = max(c.m[i][j],a.m[i][k] + b.m[k][j]);

		return c;

	}

};

int n,m;

#define MAXN 100010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int val[MAXN];

int dep[MAXN],fa[MAXN],siz[MAXN],son[MAXN],top[MAXN],bot[MAXN];

int rnk[MAXN],th[MAXN],tot = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth;siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;rnk[k] = ++tot;th[tot] = k;

	if(son[k] == 0)

	{

		bot[top[k]] = k;

		return;

	}

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

ll f[MAXN][2],g[MAXN][2];

bool vis[MAXN];

void dp(int k)

{

	vis[k] = true;

	f[k][0] = g[k][0] = 0;

	f[k][1] = g[k][1] = val[k];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dp(e[i].to);

		f[k][0] += max(f[e[i].to][0],f[e[i].to][1]);

		f[k][1] += f[e[i].to][0];

		if(e[i].to == son[k])continue;

		g[k][0] += max(f[e[i].to][0],f[e[i].to][1]);

		g[k][1] += f[e[i].to][0];

	}

	return;

}

struct node

{

	int lc,rc;

	matrix s;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)

	{

		t[rt].s.m[0][0] = t[rt].s.m[0][1] = g[th[l]][0];

		t[rt].s.m[1][0] = g[th[l]][1];

		t[rt].s.m[1][1] = -INF;

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	t[rt].s = t[t[rt].lc].s * t[t[rt].rc].s;

	return;

}

matrix query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].s;

	if(R <= mid)return query(t[rt].lc,L,R,l,mid);

	if(L > mid)return query(t[rt].rc,L,R,mid + 1,r);

	return query(t[rt].lc,L,R,l,mid) * query(t[rt].rc,L,R,mid + 1,r);

}

void maintain(int rt,int p,int l,int r)

{

	if(l == r)

	{

		t[rt].s.m[0][0] = t[rt].s.m[0][1] = g[th[p]][0];

		t[rt].s.m[1][0] = g[th[p]][1];

		t[rt].s.m[1][1] = -INF;

		return;

	}

	if(p <= mid)maintain(t[rt].lc,p,l,mid);

	else maintain(t[rt].rc,p,mid + 1,r);

	t[rt].s = t[t[rt].lc].s * t[t[rt].rc].s;

	return;

}

void modify(int k,int v)

{

	g[k][1] += v - val[k];

	val[k] = v;

	while(k != 0)

	{

		matrix a = query(root,rnk[top[k]],rnk[bot[top[k]]],1,n);

		maintain(root,rnk[k],1,n);

		matrix b = query(root,rnk[top[k]],rnk[bot[top[k]]],1,n);

		k = fa[top[k]];

		g[k][1] += b.m[0][0] - a.m[0][0];

		g[k][0] += max(b.m[0][0],b.m[1][0]) - max(a.m[0][0],a.m[1][0]);

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&val[i]);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dfs1(1,1);dfs2(1,1);

	dp(1);

	build(root,1,n);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		modify(a,b);

		matrix res = query(root,rnk[1],rnk[bot[1]],1,n);

		printf("%lld\n",max(res.m[0][0],res.m[1][0]));

	}

	return 0;

}