Luogu P3591 [POI2015]ODW 题解

(Updated: )
oi
,

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$。

若$c\leq S$，则预处理出答案，前缀和一下即可。

若$c>S$，则直接暴力跳。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#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);
}
}
}