https://loj.ac/problem/2322

先吐槽一下，sb数据毁我青春败我前程。

首先，一个数开根开不了多少次。

当我们把它开到1的时候，我们以后就不需要开他了，我们可以利用并查集跳过他，这是套路。

但是这个每次走$k$步，让人很头痛。

于是乎……分块

首先，对于$k$比较大的情况，我们可以暴力跳。否则，

我们对于每个$k$建一棵树，第$i$棵树上$x$的父亲是原树上$x$的第$i$个祖先

然后树剖，用线段树或者树状数组维护一下就好了。

然后！！打开榜，rk1，啥子，并查集+暴力跳？！

诶，那就暴力跳吧。

//Serene
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i) #define Rep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=1e5+7,maxs=200+7,maxt=23,W=19;
ll n,m,a[maxn],s;

char cc;ll ff;
templatevoid read(T& aa) {
aa=0;cc=getchar();ff=1;
while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
if(cc=='-') ff=-1,cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
aa*=ff;
}

int fir[maxn],nxt[maxn],to[maxn],e=0;
void add(int x,int y) {
to[++e]=y;nxt[e]=fir[x];fir[x]=e;
to[++e]=x;nxt[e]=fir[y];fir[y]=e;
}

int f[maxn];
int find(int x) {return x==f[x]? x:f[x]=find(f[x]);}

int fa[maxn][maxt],jp[maxn][maxs],dep[maxn];
void dfs(int pos,int f) {
int y,z; dep[pos]=dep[f]+1;
fa[pos][0]=jp[pos][1]=f; jp[pos][0]=pos;
For(i,1,W) fa[pos][i]=fa[fa[pos][i-1]][i-1];
For(i,2,s) jp[pos][i]=jp[f][i-1];
for(y=fir[pos];y;y=nxt[y]) {
if((z=to[y])==f) continue;
dfs(z,pos);
}
}

inline int get_fa(int x,int k) {
if(k<=s) return jp[x][k]; Rep(i,W,0) if(k>=(1<<i)) {x=fa[x][i]; k-=(1<<i);}
return x;
}

int get_lca(int x,int y) {
if(dep[x]!=dep[y]) {
if(dep[x]=dep[y]) x=fa[x][i];
}
if(x==y) return x;
Rep(i,W,0) if(fa[x][i]!=fa[y][i]) {x=fa[x][i]; y=fa[y][i];}
return fa[x][0];
}

void chge(int x) {
if(a[x]==1) return;
a[x]=floor(sqrt(a[x]));
if(a[x]==1) f[x]=find(fa[x][0]);
}

int q(int x,int y,int lca,int k) {
if(dep[y]-dep[lca]>=k) return get_fa(y,k);
k-=dep[y]-dep[lca]; y=lca;
return get_fa(x,dep[x]-dep[y]-k);
}

inline int lst(int x,int k) {
if(k>s) return get_fa(x,k);
int y=find(fa[x][0]);
int p=(dep[x]-dep[y])%k;
if(p) p=k-p;
return jp[y][p];
}

void get_chge(int x,int y,int k) {
int lca=get_lca(x,y),len=dep[x]+dep[y]-2*dep[lca];
if(len%k) chge(y),y=q(x,y,lca,len%k),lca=get_lca(x,y);
while(dep[x]>=dep[lca]) {chge(x); x=lst(x,k);}
while(dep[y]>dep[lca]) {chge(y); y=lst(y,k);}
}

ll Yth(int x,int y,int k) {
int lca=get_lca(x,y),len=dep[x]+dep[y]-2*dep[lca]; ll rs=0;
if(len%k) rs+=a[y],y=q(x,y,lca,len%k),lca=get_lca(x,y);
rs+=(dep[x]+dep[y]-2*dep[lca])/k+1;
while(dep[x]>=dep[lca]) {rs+=a[x]-1; x=lst(x,k);}
while(dep[y]>dep[lca]) {rs+=a[y]-1; y=lst(y,k);}
return rs;
}

int main() {
read(n); int op,x,y,k;
s=min(200,(int)sqrt(n)+1);
For(i,1,n) read(a[i]),f[i]=i;
For(i,1,n-1) {
read(x); read(y);
add(x,y);
}
dfs(1,0); read(m);
For(i,1,n) if(a[i]==1) f[i]=fa[i][0];
For(i,1,m) {
read(op); read(x); read(y); read(k);
if(op==0) get_chge(x,y,k);
else printf("%lld\n",Yth(x,y,k));
}
return 0;
}