#根号分治，树上倍增#洛谷 3591 [POI2015]ODW

题目

---

分析

考虑直接用倍增跳会TLE，设(f[x][i])表示以(x)为起点每次跳(i)步的点权和，
这可以预处理出来，综合一下两种做法，当(i>sqrt{n})时直接上倍增，否则预处理(f)即可
如果用长链剖分求树上(k)级祖先那么就可以去掉(log)

---

代码

#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=50011,M=224;
typedef long long lll; lll g[N][M];
struct node{int y,next;}e[N<<1];
int f[N][16],n,LCA[N],a[N],b[N],p[N],as[N],et=1,F[M],dep[N];
inline signed iut(){
	rr int ans=0,f=1; rr char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans*f;
}
inline void print(lll ans){
	if (ans>9) print(ans/10);
	putchar(ans%10+48);
} 
inline void dfs(int x,int fa){
	f[x][0]=fa,F[0]=x,dep[x]=dep[fa]+1;
	for (rr int i=1;i<16&&f[x][i-1];++i)
	    f[x][i]=f[f[x][i-1]][i-1];
	for (rr int i=1;i<M;++i) F[i]=f[F[i-1]][0];
	for (rr int i=1;i<M;++i) g[x][i]=g[F[i]][i]+a[x];
	for (rr int i=as[x];i;i=e[i].next)
	    if (e[i].y!=fa) dfs(e[i].y,x);
}
inline signed lca(int x,int y){
	if (dep[x]<dep[y]) x^=y,y^=x,x^=y;
	for (rr int i=15;~i;--i)
	    if (dep[f[x][i]]>=dep[y]) x=f[x][i];
	if (x==y) return x;
	for (rr int i=15;~i;--i)
	if (f[x][i]!=f[y][i])
	    x=f[x][i],y=f[y][i];
    return f[x][0];
}
inline signed Get(int x,int y){
	for (rr int i=15;~i;--i)
	    if ((y>>i)&1) x=f[x][i];
	return x;
}
inline lll answ(int x,int LCA,int y,int P){
	rr lll ans=0;
	if (P>=M){
		ans+=a[x];
		for (;dep[x]-P>=dep[LCA];)
		    ans+=a[x=Get(x,P)];
		rr int now=dep[x]-dep[LCA];
		if (now&&P-now>dep[y]-dep[LCA]) ans+=a[y];
		else{
			x=Get(y,dep[y]-dep[LCA]-P*(now>0)+now);
			if (x!=LCA) ans+=a[x];
			for (;dep[x]+P<=dep[y];)
			    x=Get(y,dep[y]-dep[x]-P),ans+=a[x];
			if (x!=y) ans+=a[y];
		}
	}else{
		rr int step=(dep[x]-dep[LCA])/P;
		ans+=g[x][P]-g[Get(x,(step+1)*P)][P];
		rr int now=dep[x]-dep[LCA]-P*step;
		if (now&&P-now>dep[y]-dep[LCA]) ans+=a[y];
		else{
			x=Get(y,dep[y]-dep[LCA]-P*(y!=LCA)+now);
			step=(dep[y]-dep[x])/P;
			rr int t=Get(y,dep[y]-dep[x]-step*P);
			if (t!=LCA) ans+=g[t][P]-g[Get(x,P)][P];
			if (t!=y) ans+=a[y];
		}
	}
	return ans;
}
signed main(){
	n=iut();
	for (rr int i=1;i<=n;++i) a[i]=iut();
	for (rr int i=1;i<n;++i){
		rr int x=iut(),y=iut();
		e[++et]=(node){y,as[x]},as[x]=et;
		e[++et]=(node){x,as[y]},as[y]=et;
	}
	dfs(1,0);
	for (rr int i=1;i<=n;++i) b[i]=iut();
	for (rr int i=1;i<n;++i) p[i]=iut(),LCA[i]=lca(b[i],b[i+1]);
	for (rr int i=1;i<n;++i) print(answ(b[i],LCA[i],b[i+1],p[i])),putchar(10);
	return 0;
}