目录

---

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

input

第一行包含一个正整数 n(2<=n<=50000)。表示节点的个数。

第二行包含 n 个正整数，其中第 i 个数为 a，分别表示每个点的权值。

接下来 n-1 行，每行包含两个正整数 u, v(1<=u,v<=n)，表示u与v之间有一条边。

接下来一行包含 n 个互不相同的正整数，其中第i个数为 b，表示行走路线。

接下来一行包含 n-1 个正整数，其中第 i 个数为 c，表示每次行走的步伐大小。

output

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

sample input

5

1 2 3 4 5

1 2

2 3

3 4

3 5

4 1 5 2 3

1 3 1 1

sample output

10

6

10

5

@solution@

通过一些简单的树上差分，可以转换为这样一个问题：

若干次询问，第 i 次询问某个点 xi 到根的路径上深度 mod mi = ci 的点的权值和。

一个比较经典的模型。我们将 mi 分两类处理：

（1）\(mi \le \sqrt n\)，此时 (mi, ci) 这样一个二元组的数量只有 O(n) 个。我们将这些二元组暴力存下来，每一次加入一个点用 \(O(\sqrt n)\) 的时间去更新。

（2）\(mi > \sqrt n\)，此时满足要求的点数量为 \(O(\frac{n}{mi}) = O(\sqrt n)\)，暴力将这些点找出来即可。

离线处理，采用 dfs 去统计信息并回答询问。

时间复杂度，第一类为 \(O(n) + O(n\sqrt n)\)，第二类为 \(O(n\sqrt n) + O(n)\)。其中前者为询问复杂度，后者为统计信息的复杂度。

总时间复杂度 \(O(n\sqrt n)\)。

@accepted code@

#include
    
     #include
     
      #include
      
       using namespace std;const int MAXN = 50000;const int SQRT = 250;struct edge{    int to; edge *nxt;}edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt = &edges[0];void addedge(int u, int v) {    edge *p = (++ecnt);    p->to = v, p->nxt = adj[u], adj[u] = p;}int dep[MAXN + 5], fa[20][MAXN + 5];void dfs(int rt, int pre) {    dep[rt] = dep[pre] + 1, fa[0][rt] = pre;    for(int i=1;i<20;i++)        fa[i][rt] = fa[i-1][fa[i-1][rt]];    for(edge *p=adj[rt];p;p=p->nxt)        if( p->to != pre ) dfs(p->to, rt);}int lca(int u, int v) {    if( dep[u] < dep[v] ) swap(u, v);    for(int i=19;i>=0;i--)        if( dep[fa[i][u]] >= dep[v] )            u = fa[i][u];    if( u == v ) return u;    for(int i=19;i>=0;i--)        if( fa[i][u] != fa[i][v] )            u = fa[i][u], v = fa[i][v];    return fa[0][u];}struct query{    int m, r, f;    int num;    query(int _m=0, int _r=0, int _f=0, int _n=0):m(_m), r(_r), f(_f), num(_n){}};vector
       
        qry[MAXN + 5];int a[MAXN + 5], b[MAXN + 5], c[MAXN + 5];int ans[MAXN + 5], arr[MAXN + 5];int res[SQRT + 5][SQRT + 5];void dfs2(int x) {    arr[dep[x]] = a[x];    for(int i=1;i<=SQRT;i++)        res[i][dep[x]%i] += a[x];    for(int i=0;i
        
         nxt)        dfs2(p->to);    for(int i=1;i<=SQRT;i++)        res[i][dep[x]%i] -= a[x];}int main() {    int n; scanf("%d", &n);    for(int i=1;i<=n;i++) scanf("%d", &a[i]);    for(int i=1;i
        
       
      
     
    

@details@

看到网上题解说树链剖分什么的，我只想说：

果然离线处理 + 差分好啊，一个 dfs 搞定的事情。