题目描述
给定一棵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统计出每一次行走时经过的所有点的权值和。
输入格式
第一行包含一个正整数n(2<=n<=50000)。表示节点的个数。第二行包含n个正整数，其中第i个数为ai，分别表示每个点的权值。接下来n-1行，每行包含两个正整数u,v(1<=u,v<=n)，表示u与v之间有一条边。接下来一行包含n个互不相同的正整数，其中第i个数为bi，表示行走路线。接下来一行包含n-1个正整数，其中第i个数为ci，表示每次行走的步伐大小。
输出格式
包含n-1行，每行一个正整数，依次输出每次行走时经过的所有点的权值和
输入输出样例
输入 #1复制
5 1 2 3 4 5 1 2 2 3 3 4 3 5 4 1 5 2 3 1 3 1 1
输出 #1复制
10 6 10 5
说明/提示
给定一棵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统计出每一次行走时经过的所有点的权值和。
分析
看到n的大小就不难想到要用到分块。于是我们可以按步伐大于根号n和小于根号n将询问分为两类。对于大于根号n的部分，我们只要每次暴力跳即可。小于根号n的部分就预处理。
具体实现起来就是，预处理up[x,y]表示从点x开始每次跳y步直到不能跳为止的权值和，然后便可以O(logn)处理第二部分的询问。
对于暴力跳而言，也就是要支持快速查找第k级祖先，这有一个经典的长链剖分做法，但放在这题中是可以用重链剖分来实现的。在找一个点的k级祖先时，若k级祖先在当前重链上，就根据其在dfs序中的位置直接得到祖先，否则就暴力往上跳。那么处理询问的总复杂度就是O(logn+sqrtn)。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
typedef unsigned long long ULL;const ULL INF=(ULL)0-(ULL)1;const int N = 1e5+5;
int a[N],b[N],c[N];
int up[N][235],block;;
int n;
int w[N];
int head[N], cnt;
int num;
int root[N];//保存结点 u 的父亲节点
int depth[N]; //保存结点 u 的深度值
int W_son[N];//保存重儿子
int size[N]; //保存以 u 为根的子树节点个数
int top[N];//保存当前节点所在链的顶端节点
int id[N];//保存树中每个节点剖分以后的新编号（ DFS 的执行顺序）
int new_W[N]; //保存当前 dfs 标号在树中所对应的节点
int dfn[N];// 保存dfs序，dfn[i]表示dfs序号为i的原数组下标struct Eddge
{int nex, to;
} edge[N<<1];//这里卡了好久，一定要乘以2
void addEddge(int u, int v)
{edge[++cnt].to=v;edge[cnt].nex=head[u];head[u] = cnt;
}
void dfs1(int u, int fa, int deep)
{depth[u] = deep;root[u] = fa;size[u] = 1;int v=u;for (int i=1; i<=block; i++)v=root[v],up[u][i]=a[u]+up[v][i];int maxSon = -1;for(int i=head[u]; i!=-1; i=edge[i].nex){int v = edge[i].to;if(v == fa)continue;dfs1(v, u, deep+1);size[u] += size[v];if(size[v] > maxSon){maxSon = size[v];W_son[u] = v;}}
}
void dfs2(int u, int topf)
{id[u] = ++num;dfn[num]=u;new_W[num] = a[u];top[u] = topf;if(!W_son[u])return;dfs2(W_son[u], topf);for(int i=head[u]; i!=-1; i=edge[i].nex){int v = edge[i].to;if(v == W_son[u] || v == root[u])continue;dfs2(v, v);}
}int get_lca(int x,int y)
{while (top[x]!=top[y]){if (depth[top[x]]<depth[top[y]])swap(x,y);x=root[top[x]];}return depth[x]<depth[y]?x:y;
}
//获取x的k级祖先
int get_kth(int x,int k)
{while (x&&depth[x]-depth[top[x]]<k)k-=depth[x]-depth[top[x]]+1,x=root[top[x]];return !x?0:dfn[id[x]-k];
}void init()
{cnt = num = 0;memset(head, -1, sizeof(head));memset(W_son, 0, sizeof(W_son));
}int main()
{init();n=read();block=sqrt(n);for (int i=1; i<=n; i++)a[i]=read();for (int i=1; i<n; i++){int x=read(),y=read();addEddge(x,y);addEddge(y,x);}for (int i=1; i<=n; i++)b[i]=read();for (int i=1; i<n; i++)c[i]=read();dfs1(1,0,1);dfs2(1,1);for (int i=1; i<n; i++){int x=b[i],y=b[i+1],z=c[i],lca=get_lca(x,y);if (z<=block){int ans=up[x][z]-up[get_kth(lca,z-(depth[x]-depth[lca])%z)][z];int tmp=get_kth(y,(depth[x]+depth[y]-depth[lca]*2)%z);if (depth[tmp]>=depth[lca])ans+=up[tmp][z]-up[get_kth(lca,z-(depth[tmp]-depth[lca])%z)][z];if ((depth[x]+depth[y]-depth[lca]*2)%z>0)ans+=a[y];if ((depth[x]-depth[lca])%z==0)ans-=a[lca];printf("%d\n",ans);}else{int ans=0,tmp=x;while (depth[tmp]>=depth[lca])ans+=a[tmp],tmp=get_kth(tmp,z);tmp=get_kth(y,(depth[x]+depth[y]-depth[lca]*2)%z);while (depth[tmp]>=depth[lca])ans+=a[tmp],tmp=get_kth(tmp,z);if ((depth[x]+depth[y]-depth[lca]*2)%z>0)ans+=a[y];if ((depth[x]-depth[lca])%z==0)ans-=a[lca];printf("%d\n",ans);}}return 0;
}