Luogu P3591 [POI2015]ODW 题解
Description
题目链接
给定一棵n个点的树，树上每条边的长度都为1，第i个点的权值为a[i]。Byteasar想要走遍这整棵树，他会按照某个1到n的全排列b走n-1次，第i次他会从b[i]点走到b[i 1]点，并且这一次的步伐大小为c[i]。对于一次行走，假设起点为x，终点为y，步伐为k，那么Byteasar会从x开始，每步往前走k步，如果最后不足k步就能到达y，那么他会一步走到y。请帮助Byteasar统计出每一次行走时经过的所有点的权值和。
Solution
设一个阈值S=sqrt N。
若cleq S，则预处理出答案，前缀和一下即可。
若c>S
Code
代码语言：javascript复制#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("%dn",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("%dn",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("%dn",Ans);
}
}
}
