Luogu P3591 [POI2015]ODW 题解

#include<cstdio>
#define S 225
int n,a[50010],b[50010],c[50010],fir[50010],nxt[50010<<1],son[50010<<1],tot,sum[50010],dep[50010],f[50010][20],s[50010][233];
inline void add(int x,int y){++tot,nxt[tot]=fir[x],fir[x]=tot,son[tot]=y;}
inline void dfs0(int x){
sum[x]+=a[x];
for(int i=0;i<16;i++) f[x][i+1]=f[f[x][i]][i];
for(int to,i=fir[x];i;i=nxt[i]){
to=son[i];
if(dep[to]) continue ;
dep[to]=dep[x]+1;
f[to][0]=x;
sum[to]=sum[x];
dfs0(to);
}
}
inline int getlca(int x,int y){
if(dep[x]<dep[y]) x^=y^=x^=y;
for(int i=16;~i;i--)
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
if(x==y) return x;
for(int i=16;~i;i--)
if(f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
inline int getfa(int x,int d){
for(int i=16;~i;i--)
if(d>>i&1) x=f[x][i];
return x;
}
inline void dfs(int x){
int fa=f[x][0];
for(int i=2;i<=S;i++) fa=f[fa][0],s[x][i]=s[fa][i]+a[x];
for(int to,i=fir[x];i;i=nxt[i]){
to=son[i];
if(dep[x]<dep[to]) dfs(to);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int x,y,i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<n;i++) scanf("%d",&c[i]);
dep[1]=1;dfs0(1);
dfs(1);
for(int x,y,k,lca,i=1;i<n;i++){
x=b[i],y=b[i+1],k=c[i],lca=getlca(x,y);
if(k==1) printf("%d\n",sum[x]+sum[y]-sum[lca]-sum[f[lca][0]]);
else if(k<=S){
int Ans=s[x][k],d=(dep[x]-dep[lca])%k==0?k:(dep[x]-dep[lca])%k;
for(int i=16;~i;i--)
if(dep[f[x][i]]-dep[lca]>=d) x=f[x][i];
Ans+=a[x]-s[x][k];
if(dep[x]+dep[y]-(dep[lca]<<1)>=k){
d=k-dep[x]+dep[lca];
x=y;
for(int i=16;~i;i--)
if(dep[f[x][i]]-dep[lca]>=d) x=f[x][i];
d=(dep[y]-dep[x])%k;
if(d) Ans+=a[y];
y=getfa(y,d);
Ans+=s[y][k]-s[x][k]+a[x];
}else Ans+=a[y];
printf("%d\n",Ans);
}else{
int Ans=0;
while(dep[x]-dep[lca]>k) Ans+=a[x],x=getfa(x,k);
Ans+=a[x];
if(dep[x]+dep[y]-(dep[lca]<<1)>=k){
int d=k-dep[x]+dep[lca];
x=y;
for(int i=16;~i;i--)
if(dep[f[x][i]]-dep[lca]>=d) x=f[x][i];
d=(dep[y]-dep[x])%k;
if(d) Ans+=a[y];
y=getfa(y,d);
while(dep[y]-dep[x]>=k) Ans+=a[y],y=getfa(y,k);
Ans+=a[y];
}else Ans+=a[y];
printf("%d\n",Ans);
}
}
}