#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <cassert>
#define rf freopen("in.in", "r", stdin)
#define wf freopen("out.out", "w", stdout)
#define rep(i, s, n) for(int i=int(s); i<=int(n); ++i)
using namespace std;
const int mx = 1e5 + 10, mod = 1e9+7;
#define mp make_pair
#define pi pair<int, int>
#define ms(a, v) memset(a, int(v), sizeof(a))
static int C[mx], A, B, P;
int n, t, q, qs, qe, val, chno=1, idx=0;
int neg_inf = -2e9;
static int pos[mx], wc[mx], chain[mx], leaf_val[mx],
l[mx], lca[mx][20], ch[mx], vis[mx], p[mx];
struct node
{
int max_alive, number_alive, lazy_update_val;
} st[mx*4];
vector<int> g[mx];
int cmp(int l, int r)
{
return ch[l]>ch[r];
}
/*----------Segment tree functions-----------*/
void merge(int r)
{
st[r].number_alive = st[2*r].number_alive + st[2*r+1].number_alive;
st[r].max_alive = max(st[2*r].max_alive, st[2*r+1].max_alive) + st[r].lazy_update_val;
}
void build(int x, int y, int r)
{
if(x == y)
{
st[r].max_alive = leaf_val[x];
st[r].lazy_update_val = 0;
st[r].number_alive = (leaf_val[x] < P);
return;
}
int m = (x+y) >> 1;
st[r].lazy_update_val = 0;
build(x, m, 2*r); build(m+1, y, 2*r+1);
merge(r);
}
void up(int x, int y, int r)
{
if(y<qs or qe<x or qs>qe)
return;
if(qs<=x && y<=qe)
{
st[r].lazy_update_val += val, st[r].max_alive += val;
return;
}
int m=(x+y)>>1;
up(x, m, 2*r); up(m+1, y, 2*r+1);
merge(r);
}
void propagate(int x, int y, int r, int lazy)
{
if(st[r].max_alive + lazy < P or !st[r].number_alive)
{
st[r].max_alive += lazy;
st[r].lazy_update_val += lazy;
return;
}
if(x==y)
{
if(st[r].max_alive + lazy >= P)
st[r].max_alive = neg_inf, st[r].number_alive = 0;
return;
}
int m = (x+y)>>1;
lazy += st[r].lazy_update_val;
st[r].lazy_update_val = 0;
propagate(x, m, 2*r, lazy); propagate(m+1, y, 2*r+1, lazy);
merge(r);
}
int qu(int x, int y, int r, int lazy)
{
st[r].max_alive += lazy;
st[r].lazy_update_val += lazy;
if(y<qs || qe<x || qs>qe)
return 0;
if(qs<=x && y<=qe)
{
propagate(x, y, r, 0);
return (y-x+1) - st[r].number_alive;
}
int m = (x+y)>>1;
lazy = st[r].lazy_update_val;
st[r].lazy_update_val = 0;
int ret = qu(x, m, 2*r, lazy) + qu(m+1, y, 2*r+1, lazy);
merge(r);
return ret;
}
/*-----------------------------------------*/
/*-----------Lowest Common Ancestor---------*/
int lcanc(int x, int y)
{
if(l[x]<l[y]) swap(x, y);
while(l[x]>l[y])
{
int j=log2(l[x]-l[y]);
x=lca[x][j];
}
int j=log2(l[x]);
while(x!=y)
{
while(lca[x][j]==lca[y][j] && j)
j--;
x=lca[x][j], y=lca[y][j];
}
return x;
}
/*-----------------------------------------*/
/*-----------DFS to Preprocess---------*/
void dfs(int u)
{
vis[u]=ch[u]=1;
rep(i, 0, g[u].size()-1)
{
int v=g[u][i];
if(vis[v]) continue;
l[v]=l[u]+1;
p[v]=lca[v][0]=u;
int go=u, j=1;
while(go!=-1)
{
go=lca[v][j]=lca[go][j-1];
j++;
}
dfs(v);
ch[u]+=ch[v];
}
}
/*----------------------------------------------*/
/*------------Heavy Light Decomposition---------*/
void hld(int u)
{
wc[u]=chno;
pos[u]=++idx; leaf_val[idx] = C[u];
for(int i=1; i<g[u].size(); ++i)
{
int v=g[u][i];
if(i==1)
{
hld(v);
continue;
}
chno++;
chain[chno]=v;
hld(v);
}
}
/*------------------------------------------------*/
/*---------- UPDATE AND QUERY FUNCTIONS-----------*/
int updater(int a, int b, int chk)
{
int ret=0;
while(true)
{
if(wc[a]==wc[b])
{
qs=pos[b]+chk, qe=pos[a];
up(1, n, 1);
break;
}
int chnh=chain[wc[a]];
qs=pos[chnh], qe=pos[a];
up(1, n, 1);
a=p[chnh];
}
return ret;
}
void update(int u, int v, int w)
{
val = w;
int anc = lcanc(u, v);
updater(u, anc, 0); updater(v, anc, 1);
}
int getans(int a, int b, int chk)
{
int ret=0;
while(1)
{
if(wc[a]==wc[b])
{
qs=pos[b]+chk, qe=pos[a];
ret += qu(1, n, 1, 0);
break;
}
int chnh=chain[wc[a]];
qs=pos[chnh], qe=pos[a];
ret += qu(1, n, 1, 0);
a=p[chnh];
}
return ret;
}
int query(int u, int v)
{
int anc = lcanc(u, v);
return getans(u, anc, 0) + getans(v, anc, 1);
}
/*----------------------------------------------*/
int main()
{
//rf; wf;
scanf("%d", &t);
while(t--)
{
scanf("%d %d %d %d", &n, &q, &A, &B);
if(A == 0)
P = (B>=0)? neg_inf: -1*neg_inf;
else
P = (B < 0)? ceil((-1.0*B)/A): (-B)/A;
rep(i, 0, n)
{
g[i].clear(), vis[i]=0, ch[i]=0;
rep(j, 0, 19)
lca[i][j]=-1;
}
g[1].push_back(0);
vis[0]=1, ch[0]=1e9;
rep(i, 1, n)
scanf("%d", &C[i]);
rep(i, 1, n-1)
{
int u, v;
scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
rep(i, 1, n)
sort(g[i].begin(), g[i].end(), cmp);
chno=1, idx=0; chain[1]=1;
hld(1);
build(1, n, 1);
while(q--)
{
int type, u, v, w;
scanf("%d %d %d", &type, &u, &v);
if(type == 1)
scanf("%d", &w),
update(u, v, w);
else
printf("%d\n", query(u, v));
}
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPGNhc3NlcnQ+CiNkZWZpbmUgcmYgZnJlb3BlbigiaW4uaW4iLCAiciIsIHN0ZGluKQojZGVmaW5lIHdmIGZyZW9wZW4oIm91dC5vdXQiLCAidyIsIHN0ZG91dCkKI2RlZmluZSByZXAoaSwgcywgbikgZm9yKGludCBpPWludChzKTsgaTw9aW50KG4pOyArK2kpCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGludCBteCA9IDFlNSArIDEwLCBtb2QgPSAxZTkrNzsKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBwaSBwYWlyPGludCwgaW50PgojZGVmaW5lIG1zKGEsIHYpIG1lbXNldChhLCBpbnQodiksIHNpemVvZihhKSkKCnN0YXRpYyBpbnQgQ1tteF0sIEEsIEIsIFA7CmludCBuLCB0LCBxLCBxcywgcWUsIHZhbCwgY2hubz0xLCBpZHg9MDsKaW50IG5lZ19pbmYgPSAtMmU5OwoKc3RhdGljIGludCBwb3NbbXhdLCB3Y1tteF0sIGNoYWluW214XSwgbGVhZl92YWxbbXhdLAogICAgICAgICAgIGxbbXhdLCBsY2FbbXhdWzIwXSwgY2hbbXhdLCB2aXNbbXhdLCBwW214XTsKCnN0cnVjdCBub2RlCnsKCWludCBtYXhfYWxpdmUsIG51bWJlcl9hbGl2ZSwgbGF6eV91cGRhdGVfdmFsOwp9IHN0W214KjRdOwoKdmVjdG9yPGludD4gZ1tteF07CmludCBjbXAoaW50IGwsIGludCByKQp7CglyZXR1cm4gY2hbbF0+Y2hbcl07Cn0KCi8qLS0tLS0tLS0tLVNlZ21lbnQgdHJlZSBmdW5jdGlvbnMtLS0tLS0tLS0tLSovCgp2b2lkIG1lcmdlKGludCByKQp7CglzdFtyXS5udW1iZXJfYWxpdmUgPSBzdFsyKnJdLm51bWJlcl9hbGl2ZSArIHN0WzIqcisxXS5udW1iZXJfYWxpdmU7CglzdFtyXS5tYXhfYWxpdmUgPSBtYXgoc3RbMipyXS5tYXhfYWxpdmUsIHN0WzIqcisxXS5tYXhfYWxpdmUpICsgc3Rbcl0ubGF6eV91cGRhdGVfdmFsOwp9IAoKdm9pZCBidWlsZChpbnQgeCwgaW50IHksIGludCByKQp7CglpZih4ID09IHkpCgl7CgkJc3Rbcl0ubWF4X2FsaXZlID0gbGVhZl92YWxbeF07CgkJc3Rbcl0ubGF6eV91cGRhdGVfdmFsID0gMDsKCQlzdFtyXS5udW1iZXJfYWxpdmUgPSAobGVhZl92YWxbeF0gPCBQKTsKCQlyZXR1cm47Cgl9CgoJaW50IG0gPSAoeCt5KSA+PiAxOwoJc3Rbcl0ubGF6eV91cGRhdGVfdmFsID0gMDsKCWJ1aWxkKHgsIG0sIDIqcik7IGJ1aWxkKG0rMSwgeSwgMipyKzEpOwoKCW1lcmdlKHIpOwkKfQp2b2lkIHVwKGludCB4LCBpbnQgeSwgaW50IHIpCnsKCWlmKHk8cXMgb3IgcWU8eCBvciBxcz5xZSkKCQlyZXR1cm47CgoJaWYocXM8PXggJiYgeTw9cWUpCgl7CgkJc3Rbcl0ubGF6eV91cGRhdGVfdmFsICs9IHZhbCwgc3Rbcl0ubWF4X2FsaXZlICs9IHZhbDsKCQlyZXR1cm47Cgl9CgkKCWludCBtPSh4K3kpPj4xOwoJdXAoeCwgbSwgMipyKTsgdXAobSsxLCB5LCAyKnIrMSk7CgkKCW1lcmdlKHIpOwp9Cgp2b2lkIHByb3BhZ2F0ZShpbnQgeCwgaW50IHksIGludCByLCBpbnQgbGF6eSkKewoJaWYoc3Rbcl0ubWF4X2FsaXZlICsgbGF6eSA8IFAgb3IgIXN0W3JdLm51bWJlcl9hbGl2ZSkKCXsKCQlzdFtyXS5tYXhfYWxpdmUgKz0gbGF6eTsKCQlzdFtyXS5sYXp5X3VwZGF0ZV92YWwgKz0gbGF6eTsKCQlyZXR1cm47Cgl9CgoJaWYoeD09eSkKCXsKCQlpZihzdFtyXS5tYXhfYWxpdmUgKyBsYXp5ID49IFApCgkJCXN0W3JdLm1heF9hbGl2ZSA9IG5lZ19pbmYsIHN0W3JdLm51bWJlcl9hbGl2ZSA9IDA7CgkJcmV0dXJuOwoJfQoKCWludCBtID0gKHgreSk+PjE7CglsYXp5ICs9IHN0W3JdLmxhenlfdXBkYXRlX3ZhbDsKCXN0W3JdLmxhenlfdXBkYXRlX3ZhbCA9IDA7CgoJcHJvcGFnYXRlKHgsIG0sIDIqciwgbGF6eSk7IHByb3BhZ2F0ZShtKzEsIHksIDIqcisxLCBsYXp5KTsKCW1lcmdlKHIpOwp9CgppbnQgcXUoaW50IHgsIGludCB5LCBpbnQgciwgaW50IGxhenkpCnsKCXN0W3JdLm1heF9hbGl2ZSArPSBsYXp5OwoJc3Rbcl0ubGF6eV91cGRhdGVfdmFsICs9IGxhenk7CgoJaWYoeTxxcyB8fCBxZTx4IHx8IHFzPnFlKQoJCXJldHVybiAwOwoKCWlmKHFzPD14ICYmIHk8PXFlKQoJewoJCXByb3BhZ2F0ZSh4LCB5LCByLCAwKTsKCQlyZXR1cm4gKHkteCsxKSAtIHN0W3JdLm51bWJlcl9hbGl2ZTsKCX0KCQoJaW50IG0gPSAoeCt5KT4+MTsKCWxhenkgPSBzdFtyXS5sYXp5X3VwZGF0ZV92YWw7CglzdFtyXS5sYXp5X3VwZGF0ZV92YWwgPSAwOwoKCWludCByZXQgPSBxdSh4LCBtLCAyKnIsIGxhenkpICsgcXUobSsxLCB5LCAyKnIrMSwgbGF6eSk7CgltZXJnZShyKTsKCglyZXR1cm4gcmV0Owp9Ci8qLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0qLwoKLyotLS0tLS0tLS0tLUxvd2VzdCBDb21tb24gQW5jZXN0b3ItLS0tLS0tLS0qLwppbnQgbGNhbmMoaW50IHgsIGludCB5KQp7CglpZihsW3hdPGxbeV0pIHN3YXAoeCwgeSk7Cgl3aGlsZShsW3hdPmxbeV0pCgl7CgkJaW50IGo9bG9nMihsW3hdLWxbeV0pOwoJCXg9bGNhW3hdW2pdOwoJfQoKCWludCBqPWxvZzIobFt4XSk7Cgl3aGlsZSh4IT15KQoJewoJCXdoaWxlKGxjYVt4XVtqXT09bGNhW3ldW2pdICYmIGopCgkJCWotLTsKCQl4PWxjYVt4XVtqXSwgeT1sY2FbeV1bal07Cgl9CglyZXR1cm4geDsKfQovKi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tKi8KCi8qLS0tLS0tLS0tLS1ERlMgdG8gUHJlcHJvY2Vzcy0tLS0tLS0tLSovCnZvaWQgZGZzKGludCB1KQp7Cgl2aXNbdV09Y2hbdV09MTsKCXJlcChpLCAwLCBnW3VdLnNpemUoKS0xKQoJewoJCWludCB2PWdbdV1baV07CgkJaWYodmlzW3ZdKSBjb250aW51ZTsKCgkJbFt2XT1sW3VdKzE7CgkJcFt2XT1sY2Fbdl1bMF09dTsKCgkJaW50IGdvPXUsIGo9MTsKCQl3aGlsZShnbyE9LTEpCgkJewoJCQlnbz1sY2Fbdl1bal09bGNhW2dvXVtqLTFdOwoJCQlqKys7CgkJfQoKCQlkZnModik7CgkJY2hbdV0rPWNoW3ZdOwoJfQp9Ci8qLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSovCgovKi0tLS0tLS0tLS0tLUhlYXZ5IExpZ2h0IERlY29tcG9zaXRpb24tLS0tLS0tLS0qLwoKdm9pZCBobGQoaW50IHUpCnsKCXdjW3VdPWNobm87Cglwb3NbdV09KytpZHg7IGxlYWZfdmFsW2lkeF0gPSBDW3VdOwoKCWZvcihpbnQgaT0xOyBpPGdbdV0uc2l6ZSgpOyArK2kpCgl7CgkJaW50IHY9Z1t1XVtpXTsKCQlpZihpPT0xKQoJCXsKCQkJaGxkKHYpOwoJCQljb250aW51ZTsKCQl9CgoJCWNobm8rKzsKCQljaGFpbltjaG5vXT12OwoJCWhsZCh2KTsKCX0KfQovKi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSovCgovKi0tLS0tLS0tLS0gVVBEQVRFIEFORCBRVUVSWSBGVU5DVElPTlMtLS0tLS0tLS0tLSovCgppbnQgdXBkYXRlcihpbnQgYSwgaW50IGIsIGludCBjaGspCnsKCWludCByZXQ9MDsKCXdoaWxlKHRydWUpCgl7CgkJaWYod2NbYV09PXdjW2JdKQoJCXsKCQkJcXM9cG9zW2JdK2NoaywgcWU9cG9zW2FdOwoJCQl1cCgxLCBuLCAxKTsKCQkJYnJlYWs7CgkJfQoKCQlpbnQgY2huaD1jaGFpblt3Y1thXV07CgkJCgkJcXM9cG9zW2NobmhdLCBxZT1wb3NbYV07CgkJdXAoMSwgbiwgMSk7CgkJCgkJYT1wW2NobmhdOwoJfQoJcmV0dXJuIHJldDsKfQp2b2lkIHVwZGF0ZShpbnQgdSwgaW50IHYsIGludCB3KQp7Cgl2YWwgPSB3OwoJaW50IGFuYyA9IGxjYW5jKHUsIHYpOwoJdXBkYXRlcih1LCBhbmMsIDApOyB1cGRhdGVyKHYsIGFuYywgMSk7Cn0KCmludCBnZXRhbnMoaW50IGEsIGludCBiLCBpbnQgY2hrKQp7CglpbnQgcmV0PTA7Cgl3aGlsZSgxKQoJewoJCWlmKHdjW2FdPT13Y1tiXSkKCQl7CgkJCXFzPXBvc1tiXStjaGssIHFlPXBvc1thXTsKCQkJcmV0ICs9IHF1KDEsIG4sIDEsIDApOwoJCQlicmVhazsKCQl9CgoJCWludCBjaG5oPWNoYWluW3djW2FdXTsKCQkKCQlxcz1wb3NbY2huaF0sIHFlPXBvc1thXTsKCQlyZXQgKz0gcXUoMSwgbiwgMSwgMCk7CgkJCgkJYT1wW2NobmhdOwoJfQoKCXJldHVybiByZXQ7Cn0KaW50IHF1ZXJ5KGludCB1LCBpbnQgdikKewoJaW50IGFuYyA9IGxjYW5jKHUsIHYpOwoJcmV0dXJuIGdldGFucyh1LCBhbmMsIDApICsgZ2V0YW5zKHYsIGFuYywgMSk7Cn0KLyotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tKi8KCmludCBtYWluKCkKewoJLy9yZjsgd2Y7CgkKCXNjYW5mKCIlZCIsICZ0KTsKCXdoaWxlKHQtLSkKCXsKCQlzY2FuZigiJWQgJWQgJWQgJWQiLCAmbiwgJnEsICZBLCAmQik7CgkJaWYoQSA9PSAwKQoJCQlQID0gKEI+PTApPyBuZWdfaW5mOiAtMSpuZWdfaW5mOwoJCWVsc2UKCQkJUCA9IChCIDwgMCk/IGNlaWwoKC0xLjAqQikvQSk6ICgtQikvQTsKCgkJcmVwKGksIDAsIG4pCgkJewoJCQlnW2ldLmNsZWFyKCksIHZpc1tpXT0wLCBjaFtpXT0wOwoJCQlyZXAoaiwgMCwgMTkpCgkJCQlsY2FbaV1bal09LTE7CgkJfQoJCWdbMV0ucHVzaF9iYWNrKDApOwoJCXZpc1swXT0xLCBjaFswXT0xZTk7CgkJCgkJcmVwKGksIDEsIG4pCgkJCXNjYW5mKCIlZCIsICZDW2ldKTsKCQlyZXAoaSwgMSwgbi0xKQoJCXsKCQkJaW50IHUsIHY7CgkJCXNjYW5mKCIlZCAlZCIsICZ1LCAmdik7CgkJCQoJCQlnW3VdLnB1c2hfYmFjayh2KTsKCQkJZ1t2XS5wdXNoX2JhY2sodSk7CgkJfQoKCQlkZnMoMSk7CgkJcmVwKGksIDEsIG4pCgkJCXNvcnQoZ1tpXS5iZWdpbigpLCBnW2ldLmVuZCgpLCBjbXApOwoJCQoJCWNobm89MSwgaWR4PTA7IGNoYWluWzFdPTE7CgkJaGxkKDEpOwoJCWJ1aWxkKDEsIG4sIDEpOwoKCQl3aGlsZShxLS0pCgkJewoJCQlpbnQgdHlwZSwgdSwgdiwgdzsKCQkJc2NhbmYoIiVkICVkICVkIiwgJnR5cGUsICZ1LCAmdik7CgoJCQlpZih0eXBlID09IDEpCgkJCQlzY2FuZigiJWQiLCAmdyksCgkJCQl1cGRhdGUodSwgdiwgdyk7CgkJCWVsc2UKCQkJCXByaW50ZigiJWRcbiIsIHF1ZXJ5KHUsIHYpKTsKCQl9Cgl9CglyZXR1cm4gMDsKfQ==