Odwiedziny[POI 2015]

时间:2024-01-15 21:35:32

题目描述

给定一棵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统计出每一次行走时经过的所有点的权值和。

输入

  • Line 1:一个正整数n(2<=n<=50000)。表示节点的个数。
  • Line 2:n个正整数,其中第i个数为ai(1≤ai≤10000),分别表示每个点的权值。
  • Line 3~n+1:包含两个正整数u,v(1≤u,v≤n),表示u与v之间有一条边。
  • Line n+2:n个互不相同的正整数,其中第i个数为b[i](1≤b[i]≤n),表示行走路线。
  • Line n+3:n-1个正整数,其中第i个数为ci(1≤ci<n),表示每次行走的步伐大小。

输出

包含n-1行,每行一个正整数,依次输出每次行走时经过的所有点的权值和

SOL:

我们观察了一波局势,发现这道题有些眼熟。相比大家应该都做过这样一道题:给你一个静态的序列(所谓静态是指这个区间不会做任何的修改),M次给出X,L,K,让你求从X起的L个数的和,这L个数中间两两下表相间K(举个栗子:X=5,L=4,K=3,那么sum=a5+a8+a11+a14)。(N<=10W,M<=10W)

这道题我们的思想就是分块,我们发现当K很大时,我们暴力求和的速度是相当快的。因为我们发现 L<=N/K,我们的暴力复杂度是O(L)的。而K很小时,暴力就很慢了,接近于O(N)。我们又注意到K=1时便是前缀和,可以做到O(1)查询。那么我们不禁想当K很小时我们用前缀和优化(K>1有间距的前缀和相比大家都会)。

我们假设我们采取这样的策略,当K<S时我们用前缀和,K>S时我们采取暴力,那么我们就可以在最坏情况下O(n*s+m*n/s)下解决问题,那么我们解得S=sqrt N时最优。(实际上S取的稍微小一些会更快,因为我们刚刚计算的是最坏情况)

那么我们就可以做这一道题了,同样的思想,当K<sqrt N 时我们预处理,K > sqrt N 时我们便暴力向上跳。

case 1: K<sqrt N 我们预处理每个点 以K为间距向上跳的 答案,x的答案加上y的答案减去lca的答案就是了。

case 1: K>sqrt N 我们暴力做,我们每次用树上倍增的方法 log N 的方法向上跳,暴力统计答案,跳跳就好了。

看代码:

#include<bits/stdc++.h>
#define sight(c) ('0'<=c&&c<='9')
#define eho(x) for (int i=head[x];i;i=net[i])
#define N 50007
#define BRE 237
#define SIZ 21
int a[N],fall[N<<],net[N<<],head[N],tot,f[SIZ][N],dep[N],val[N][BRE],g[BRE][N],
m,rog,ot,r,ans,n,x,y,len[N],k;
inline void read(int &x){
static char c;
for (c=getchar();!sight(c);c=getchar());
for (x=;sight(c);c=getchar()) x=x*+c-;
}
using namespace std;
inline void add(int x,int y){fall[++tot]=y; net[tot]=head[x]; head[x]=tot;}
void dfs(int x,int fa){
f[][x]=fa;dep[x]=dep[fa]+;
eho(x) if(fall[i]^fa) dfs(fall[i],x);
}
void Dfs(int x){
for (int i=;i<=m;i++) val[x][i]=val[g[i][x]][i]+a[x];
eho(x) if (fall[i]^f[][x]) Dfs(fall[i]);
}
void write(int x){if (x<) {putchar(''+x); return;} write(x/); putchar(''+x%);}
inline void writeln(int x){ if (x<) putchar('-'),x*=-; write(x); putchar('\n'); }
inline int lca(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
for (int i=SIZ-;~i;i--) if (dep[f[i][x]]>=dep[y]) x=f[i][x];
if (x==y) return x;
for (int i=SIZ-;~i;i--) if (f[i][x]^f[i][y]) x=f[i][x],y=f[i][y];
return f[][x];
}
inline int up(int x,int k) {if (k<=m)return g[k][x];for (int i=SIZ-;~i;i--) if ((k>>i)&) x=f[i][x];return x;}
inline int rop(int x,int y,int k) {
if (dep[x]<dep[y]) return ;rog=;
if (k<m) {
rog+=val[x][k]; ot=k-(dep[x]-dep[y])%k; rog-=val[k==ot?y:up(y,ot%k)][k];
} else while (dep[x]>dep[y]) rog+=a[x],x=up(x,k);
return rog;
}
void solve(int x,int y,int k){
int L=lca(x,y); r=(dep[x]+dep[y]-(dep[L]<<))%k;
ans=rop(x,L,k);
if (r) ans+=a[y],y=up(y,k);
ans+=rop(y,f[][L],k);
writeln(ans);
}
int main () {
freopen("a.in","r",stdin);
read(n); m=min((int)sqrt(n),BRE-);
for (int i=;i<=n;i++) read(a[i]),g[][i]=a[i];
for (int i=n-;i;i--) read(x),read(y),add(x,y),add(y,x);
dfs(,);
for (int j=;j<SIZ;j++)
for (int i=;i<=n;i++) f[j][i]=f[j-][f[j-][i]];
memcpy(g[],f[],sizeof f[]);
for (int j=;j<=m;j++)
for (int i=;i<=n;i++) g[j][i]=g[][g[j-][i]];
Dfs();
for (int i=;i<=n;i++) read(len[i]);
for (int i=;i<n;i++) read(k),
solve(len[i],len[i+],k);
return ;
}