树链剖分 + 根号分块

Table of Contents

  1. Description
  2. Solution

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

看起来是个全排列但并没有什么性质，只能在线回答的。

所以其实这题可以随便问。

点数并不大，没有到log的地步，就想到一些根号的奇技淫巧，大于阈值的暴力跳，小于阈值的预处理。

又口胡完了实现细节何其多。为了让答案是准确的，我们要精确控制跳的距离，所以在重链上按照DFS序跳。这样就实现了小于阈值$logN$, 大于阈值$\sqrt{N}$的单次复杂度.

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>

using namespace std;

const int maxn = 50005;

struct edge
{
  int to, nxt;
}e[maxn << 1];
int n, lim, ptr, lnk[maxn], a[maxn], b[maxn], c[maxn];
int f[maxn][250], s[maxn][250];
int dep[maxn], top[maxn], fa[maxn], siz[maxn], mxson[maxn];
int dfn[maxn], rev[maxn], cnt;

inline void add(int bgn, int end) {
  e[++ptr] = (edge){end, lnk[bgn]};
  lnk[bgn] = ptr;
}
void dfs(int x, int d) {
  dep[x] = d;
  siz[x] = 1;
  f[x][1] = fa[x];
  s[x][1] = s[f[x][1]][1] + a[x];
  for (int i = 2; i < lim; ++i) {
    f[x][i] = fa[f[x][i - 1]];
    s[x][i] = s[f[x][i]][i] + a[x];
  }
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == fa[x]) continue;
    fa[y] = x;
    dfs(y, d + 1);
    siz[x] += siz[y];
    if (siz[y] > siz[mxson[x]]) mxson[x] = y;
  }
}
void dfs2(int x, int init) {
  top[x] = init;
  dfn[x] = ++cnt;
  rev[cnt] = x;
  if (!mxson[x]) return;
  dfs2(mxson[x], init);
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == mxson[x] || y == fa[x]) continue;
    dfs2(y, y);
  }
}
void init(int x) {
  f[x][1] = fa[x];
  s[x][1] = s[fa[x]][1] + a[x];
  for (int i = 2; i < lim; ++i) {
    f[x][i] = fa[f[x][i - 1]];
    s[x][i] = s[f[x][i]][i] + a[x];
  }
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == fa[x]) continue;
    init(y);
  }
}
inline int climb(int x, int dis) {
  while (dfn[x] - dfn[top[x]] < dis) {
    dis -= (dfn[x] - dfn[top[x]] + 1);
    x = fa[top[x]];
  }
  return rev[dfn[x] - dis];
}
inline int calc(int frm, int to, int step) {
  int jmp = climb(frm, dep[frm] - dep[to] - (dep[frm] - dep[to]) % step);
  //printf("--%d\n", jmp);
  if (step < lim) return s[frm][step] - s[jmp][step] + a[jmp];
  int ret = 0;
  int i;
  while (top[frm] != top[jmp]) {
    for (i = dfn[frm]; i >= dfn[top[frm]]; i -= step) ret += a[rev[i]];
    frm = climb(frm, dfn[frm] - i);
  }
  for (int i = dfn[frm]; i >= dfn[jmp]; i -= step) ret += a[rev[i]];
  return ret;
}
inline int lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    x = fa[top[x]];
  }
  return dep[x] > dep[y] ? y : x;
}
int solve(int x, int y, int step) {
  int L = lca(x, y), ret = calc(x, L, step);

  if ((dep[x] + dep[y] - 2 * dep[L]) % step) ret += a[y];
  //printf("++%d\n", ret);
  if (L == y) return ret;
  if (!((dep[x] - dep[L])%step)) ret -= a[L];
  //int res = step - (dep[x] - dep[L]) % step;
  //printf("+-%d\n", ret);
  int res = ((dep[L] - dep[x]) % step + step) % step;
  if (dep[y] - dep[L] - res < 0) return ret;
  return ret + calc(climb(y, (dep[y] - dep[L] - res) % step), L, step);
}

int main() {
  scanf("%d", &n);
  lim = sqrt(n) + 1;
  for (int i = 1; i <= n; ++i)
    scanf("%d", &a[i]);
  int u, v;
  for (int i = 1; i < n; ++i) {
    scanf("%d%d", &u, &v);
    add(u, v);
    add(v, u);
  }
  for (int i = 1; i <= n; ++i) 
    scanf("%d", &b[i]);
  for (int i = 1; i < n; ++i)
    scanf("%d", &c[i]);
  dfs(1, 1);
  dfs2(1, 1);
  //init(1);
  for (int i = 1; i < n; ++i){
    printf("%d\n", solve(b[i], b[i + 1], c[i]));
  }
  return 0;
}