---

@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 个数为 ai，分别表示每个点的权值。

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

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

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

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<cstdio>

#include<vector>

#include<algorithm>

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<query>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<qry[x].size();i++) {

		if( qry[x][i].m <= SQRT ) {

			ans[qry[x][i].num] += qry[x][i].f*res[qry[x][i].m][qry[x][i].r];

			//printf("%d %d %d\n", qry[x][i].num, x, qry[x][i].f*res[qry[x][i].m][qry[x][i].r]);

		}

		else {

			for(int j=qry[x][i].r;j<=dep[x];j+=qry[x][i].m)

				ans[qry[x][i].num] += qry[x][i].f*arr[j];

		}

	}

	for(edge *p=adj[x];p;p=p->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<n;i++) {

		int u, v; scanf("%d%d", &u, &v);

		addedge(u, v);

	}

	dfs(1, 0);

	for(int i=1;i<=n;i++) scanf("%d", &b[i]);

	for(int i=1;i<n;i++) scanf("%d", &c[i]);

	for(int i=1;i<n;i++) {

		int p = b[i], q = b[i+1], r = lca(p, q);

		qry[p].push_back(query(c[i], dep[p]%c[i], 1, i));

		qry[fa[0][r]].push_back(query(c[i], dep[p]%c[i], -1, i));

		int k = (dep[r] + c[i] - (dep[p] - dep[r])%c[i])%c[i];

		qry[q].push_back(query(c[i], k, 1, i));

		qry[r].push_back(query(c[i], k, -1, i));

		if( dep[q]%c[i] != k ) ans[i] += a[q];

	}

	dfs2(1);

	for(int i=1;i<n;i++) printf("%d\n", ans[i]);

}

@details@

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

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