Solution
在步伐$pace$比较小的时候， 我们发现用前缀和直接维护会很快
而在$pace$比较大的时候， 则暴力往上跳会最优
设$blo= \sqrt{N}$
若$pace<=blo$， 则利用前缀和更新,
预处理复杂度$O(N \sqrt{N})$， 查询复杂度$O(1)$
若$pace>blo$，则利用树剖逐渐往上跳
总共要跳$N/pace$次， 一共有$logN$条轻重链， 复杂度为$O(logN+ \sqrt{N})$
代码实现比较麻烦， 我常数写的还很差， 水平低啊QAQ
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define rd read()
#define N 50005
#define M 240
#define R register
using namespace std; int n, blo, a[N], b[N], f[N][M], sum[N][M];
int fa[N], dep[N], top[N], sz[N], son[N], id[N], idf[N], cnt;
int head[N], tot; struct edge {
int nxt, to;
}e[N << ]; inline char nc(){
static char buf[], *p1=buf, *p2=buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, , , stdin), p1 == p2) ? EOF : *p1++;
}
inline int read(){
char ch = nc();int sum = ;
while(!(ch >= '' && ch <= '')) ch = nc();
while(ch >= '' && ch <= '') sum = sum * + ch - , ch = nc();
return sum;
} inline void add(int u, int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
} inline void sw(int &A, int &B) {
A ^= B; B ^= A; A ^= B;
} inline void dfs1(R int u) {
sz[u] = ;
for (R int i = head[u]; i; i = e[i].nxt) {
R int nt = e[i].to;
if (nt == fa[u]) continue;
f[nt][] = fa[nt] = u;
dep[nt] = dep[u] + ;
dfs1(nt);
sz[u] += sz[nt];
if (sz[nt] > sz[son[u]])
son[u] = nt;
}
} inline void dfs2(R int u) {
idf[id[u] = ++cnt] = u;
if (!son[u]) return;
top[son[u]] = top[u];
dfs2(son[u]);
for (R int i = head[u]; i; i = e[i].nxt) {
R int nt = e[i].to;
if (nt == fa[u] || nt == son[u]) continue;
top[nt] = nt;
dfs2(nt);
}
} inline int LCA(R int x, R int y) {
for (;top[x] != top[y]; ) {
if (dep[top[x]] < dep[top[y]]) sw(x, y);
x = fa[top[x]];
}
if (dep[x] < dep[y]) sw(x, y);
return y;
} inline int work1(R int x, R int y, R int pace) {
R int lca = LCA(x, y), len = dep[x] + dep[y] - * dep[lca], res = ;
if (len % pace) {
res += a[y];
y = f[y][len % pace];
len -= len % pace;
}
len = dep[x] - dep[lca];
if (len % pace == ) {
res += sum[x][pace] - sum[lca][pace];
res += sum[y][pace] - sum[lca][pace];
res += a[lca];
return res;
}
R int tmp = f[lca][pace - len % pace];
res += sum[x][pace] - sum[tmp][pace];
if (dep[y] < dep[lca]) return res;
len = dep[y] - dep[lca];
tmp = f[lca][pace - len % pace];
res += sum[y][pace] - sum[tmp][pace];
return res;
} inline int up(R int x, R int d) {
R int y = top[x];
for (; x && dep[x] - dep[y] < d;) {
d -= dep[x] - dep[y] + ;
x = fa[top[x]];
y = top[x];
}
if (!x) return ;
return idf[id[x] - d];
} inline int work2(R int x, R int y, R int pace) {
R int lca = LCA(x, y), len = dep[x] + dep[y] - * dep[lca], res = ;
if (len % pace) {
res += a[y];
y = up(y, len % pace);
len -= len % pace;
}
len = dep[x] - dep[lca];
if (len % pace == ) {
while (x && dep[x] > dep[lca])
res += a[x], x = up(x, pace);
while (y && dep[y] > dep[lca])
res += a[y], y = up(y, pace);
res += a[lca];
return res;
}
while (x && dep[x] > dep[lca])
res += a[x], x = up(x, pace);
while (y && dep[y] > dep[lca])
res += a[y], y = up(y, pace);
return res;
} int main()
{
n = rd; blo = sqrt(n);
for (R int i = ; i <= n; ++i)
a[i] = rd;
for (R int i = ; i < n; ++i) {
int u = rd, v = rd;
add(u, v); add(v, u);
}
dep[] = ; dfs1();
top[] = ; dfs2();
for (R int j = ; j <= blo; ++j)
for (R int i = ; i <= n; ++i)
f[i][j] = f[f[i][j - ]][];
for (R int j = ; j <= blo; ++j)
for (R int i = ; i <= n; ++i)
sum[i][j] = a[i];
for (R int j = ; j <= blo; ++j)
for (R int i = ; i <= n; ++i) {
int x = idf[i];
sum[x][j] += sum[f[x][j]][j];
}
for (R int i = ; i <= n; ++i) b[i] = rd;
for (R int i = ; i < n; ++i) {
R int x = rd;
if (x <= blo) printf("%d\n", work1(b[i], b[i + ], x));
else printf("%d\n", work2(b[i], b[i + ], x));
}
}