题解

题目分析

这是一道算法题目，需要根据具体题目要求进行求解。

解题思路

1. 问题分析

• 仔细阅读题目描述，理解题目要求
• 分析输入输出格式和约束条件
• 确定需要使用的算法和数据结构

2. 算法选择

• 根据题目特点选择合适的算法
• 考虑时间复杂度和空间复杂度
• 确保算法能正确处理所有测试用例

3. 实现要点

• 注意边界条件的处理
• 优化输入输出以提高效率
• 确保代码的正确性和鲁棒性

4. 调试和优化

• 使用测试用例验证算法正确性
• 分析性能瓶颈并进行优化
• 确保代码能通过所有测试点

注意事项

• 仔细处理数据类型和精度问题
• 注意数组越界和空指针问题
• 确保算法的时间复杂度符合要求

#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
inline ll read(){
	ll x=0;
	int f=0,ch=0;
	while(ch<48||ch>57) f=(ch=='-'),ch=getchar();
	while(ch>47&&ch<58) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
	return f?-x:x;
}
inline void write(ll x,char end='\n'){
	if(x==0){
		putchar('0');
		putchar(end);
		return;
	}
	if(x<0) putchar('-'),x=-x;
	short ch[20]={0},cnt=0;
	while(x){
		ch[cnt++]=(short)(x%10);
		x/=10;
	}
	while(cnt--) putchar(ch[cnt]+48);
	putchar(end);
}
const int N=5e4+5;
const int M=1005,W=18;
int n,m,s;
ll a[N];
struct node{
	int to,nxt;
}e[N<<1];
int head[N],cnt;
inline void add(int u,int v){
	e[++cnt]={v,head[u]};
	head[u]=cnt;
}
int lg[N],f[N];
int dfn[N],tot;
int dep[N],topj[N][M];
int mi[19][N],fa[N][19];
inline void dfs(int u,int f){
	dep[u]=dep[f]+1;
	mi[0][dfn[u]=++tot]=f;
	fa[u][0]=f;
	for(int i=1;i<=lg[dep[u]];++i) fa[u][i]=fa[fa[u][i-1]][i-1];
	topj[u][1]=f;
	topj[u][0]=u;
	for(int i=2;i<=s;++i) topj[u][i]=topj[f][i-1];
	for(int i=head[u],v;i;i=e[i].nxt){
		v=e[i].to;
		if(v==f) continue;
		dfs(v,u);
	}
}
inline int get(int x,int y){return dfn[x]<dfn[y]?x:y;}
inline int get_lca(int u,int v){
	if(u==v) return u;
	if((u=dfn[u])>(v=dfn[v])) swap(u,v);
	int d=lg[v-u++];
	return get(mi[d][u],mi[d][v-(1<<d)+1]);
}
inline void initlca(){
	for(int i=1;i<=lg[n];++i){
		for(int j=1;j+(1<<i)-1<=n;++j)
			mi[i][j]=get(mi[i-1][j],mi[i-1][j+(1<<(i-1))]);
	}
}
inline int find(int x){return x==f[x]?x:(f[x]=find(f[x]));}
inline void change(int x){
	if(a[x]==1) return;
	a[x]=sqrt(a[x]);
	if(a[x]==1) f[x]=find(fa[x][0]);
}
inline int get_fa(int x,int k){
	if(k<=s) return topj[x][k];
	for(int i=lg[dep[x]];i>=0;--i){
		if(k>=(1<<i)){
			x=fa[x][i];
			k-=(1<<i);
		}
	}
	return x;
}
inline int query(int x,int y,int l,int k){
	if(dep[y]-dep[l]>=k) return get_fa(y,k);
	k-=dep[y]-dep[l];
	y=l;
	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 topj[y][p];
}
inline void getchange(int x,int y,int k){
	int l=get_lca(x,y);
	int len=dep[x]+dep[y]-2*dep[l];
	if(len%k){
		change(y);
		y=query(x,y,l,len%k);
		l=get_lca(x,y);
	}
	while(dep[x]>=dep[l]){
		change(x);
		x=lst(x,k);
	}
	while(dep[y]>dep[l]){
		change(y);
		y=lst(y,k);
	}
}
inline ll Yth(int x,int y,int k){
	int l=get_lca(x,y);
	int len=dep[x]+dep[y]-2*dep[l];
	ll res=0;
	if(len%k){
		res+=a[y];
		y=query(x,y,l,len%k);
		l=get_lca(x,y);
	}
	res+=(dep[x]+dep[y]-2*dep[l])/k+1;
	while(dep[x]>=dep[l]) res+=a[x]-1,x=lst(x,k);
	while(dep[y]>dep[l]) res+=a[y]-1,y=lst(y,k);
	return res;
}
int main(){
//	freopen("2.in","r",stdin);
//	freopen("my.out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i) a[i]=read(),f[i]=i;
	for(int i=1,u,v;i<n;++i){
		u=read(),v=read();
		add(u,v);add(v,u);
	}
	m=read();
	lg[0]=-1;
	for(int i=1;i<=n+1;++i) lg[i]=lg[i>>1]+1;
	s=min(1000,(int)sqrt(m*lg[n+1])+1);
	dfs(1,0);
	initlca();
	for(int i=1;i<=n;++i){
		if(a[i]==1) f[i]=fa[i][0];
	}
	int op,x,y,k;
	while(m--){
//		printf("Rest %d\n",m);
		op=read(),x=read(),y=read(),k=read();
		if(op==1) write(Yth(x,y,k));
		else getchange(x,y,k);
	}
	return 0;
}