题解几乎都使用了长链剖分，但是对于步长 $>\sqrt{n}$的块暴力跑是 $\sqrt{n}$ 的，对于步长 $<\sqrt{n}$ 的只需要 $\sqrt{n}$ 往上跳，找到离 LCA 最近的一个距离起始点长度为步长的倍数的点，然后树上差分做一下不就可以了吗，不都是 $n\sqrt{n}$ 的吗?

这是 MnZn 的代码，只过了 1,5,10

$QAQ\ !!!$

#include<bits/stdc++.h>
using namespace std;
const int M=5e4+10,N=sqrt(M)+2;
vector<int>G[M];
int fa[M],son[M],dep[M],top[M],sz[M];
int n,m;
int a[M],b[M],dis[M];
void dfs1(int u,int f){
	dep[u]=dep[f]+1;sz[u]=1;
	for(auto v:G[u]){
		if(v==f)continue;
		fa[v]=u;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]])son[u]=v;
	}
}
void dfs2(int u,int t){
	top[u]=t;
	if(son[u])dfs2(son[u],t);
	for(auto v:G[u]){
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
int LCA(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	return x;
}
int fd[M][N];
int fs[M][N];
int bls;
void init(int u){
	int x=fa[u];
	fd[u][0]=u;
//	cout<<"u:"<<u<<' '<<x<<endl;
	for(int i=1;i<=bls;i++)fd[u][i]=x,x=fa[x];
//	if(u==1)for(int i=1;i<N;i++)cout<<fd[u][i]<<' ';
//	cout<<endl;
	for(int i=1;i<=bls;i++)fs[u][i]=fs[fd[u][i]][i]+a[u];
	for(auto v:G[u]){
		if(v==fa[u])continue;
		init(v);
	}
}
int query(int x,int y,int d){
	int ans=0;
	int lca=LCA(x,y);
	if(d>=bls){
		while(dep[fd[x][d]]>=dep[lca])ans+=a[x],x=fd[x][d];
		ans+=a[x];
		while(dep[fd[x][d]]>=dep[lca])ans+=a[y],y=fd[y][d];
		ans+=a[y];
		if(x==y)ans-=a[x];
	}else{
		int dx=dep[x]-dep[lca];
		dx%=d;ans+=fs[x][d];
		int nd;
		while(dep[fd[x][bls]]-dx>=dep[lca])x=fd[x][bls];
		nd=dep[x]-dep[lca];
		x=fd[x][nd-dx];
		ans+=(a[x]-fs[x][d]);
		int dy=dep[y]-dep[lca];
		dy%=d;ans+=fs[y][d];
		while(dep[fd[y][bls]]-dy>=dep[lca])y=fd[y][bls];
		nd=dep[y]-dep[lca];
		y=fd[y][nd-dy];
		ans+=(a[y]-fs[y][d]);
		if(x==y)ans-=a[x];
	}
	return ans;
}
signed main(){
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	bls=ceil(sqrt(n));
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].push_back(y),G[y].push_back(x);
	}
	dfs1(1,0),dfs2(1,1);
	init(1);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	for(int i=1;i<n;i++)scanf("%d",&dis[i]);
	for(int i=1;i<n;i++){
		printf("%d\n",query(b[i],b[i+1],dis[i]));
	}
	return 0;
}