[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=4381
[算法]
考虑分块 ， 先设一个阈值B = 200
记Su , i表示从u节点开始 ， 每次向上跳i步 ， 所经过点的权值和 ， 可以在O(NBlogN)时间内预处理
对于每次询问 , 若k <= B ， 可以通过预处理的值求出答案 ， 否则暴力处理
时间复杂度 : O(NBlogN)(取B = 200)
[代码]
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; #define N 50010 #define M 250 #define MAXLOG 20 struct edge { int to , nxt; } e[N << 1]; int n , tot , MAGIC; int a[N] , b[N] , c[N] , father[N][MAXLOG] , depth[N] , head[N]; ll cnt[N][M]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); } template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); } template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } inline void addedge(int u , int v) { ++tot; e[tot] = (edge){v , head[u]}; head[u] = tot; } inline void work(int u , int par) { father[u][0] = par; depth[u] = depth[par] + 1; for (int i = 1; i < MAXLOG; ++i) { father[u][i] = father[father[u][i - 1]][i - 1]; } for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v == par) continue; work(v , u); } } inline int get(int u , int k) { for (int i = 0; i < MAXLOG; ++i) { if (k & (1 << i)) u = father[u][i]; } return u; } inline void dfs(int u , int par) { for (int i = 1; i <= MAGIC; ++i) { cnt[u][i] = a[u] + cnt[get(u , i)][i]; } for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v == par) continue; dfs(v , u); } } inline int lca(int x , int y) { if (depth[x] > depth[y]) swap(x , y); for (int i = MAXLOG - 1; i >= 0; --i) { if (depth[father[y][i]] >= depth[x]) y = father[y][i]; } if (x == y) return x; for (int i = MAXLOG - 1; i >= 0; --i) { if (father[x][i] != father[y][i]) x = father[x][i] , y = father[y][i]; } return father[x][0]; } int main() { read(n); for (int i = 1; i <= n; ++i) read(a[i]); for (int i = 1; i < n; ++i) { int x , y; read(x); read(y); addedge(x , y); addedge(y , x); } for (int i = 1; i <= n; ++i) read(b[i]); for (int i = 2; i <= n; ++i) read(c[i]); MAGIC = (int)sqrt(n); work(1 , 0); dfs(1 , 0); for (int i = 2; i <= n; ++i) { int x = b[i - 1] , y = b[i]; int Lca = lca(x , y); ll ans = 0; if (Lca == x) { if (c[i] <= MAGIC) { int R = (depth[y] - depth[x]) % c[i]; if (R > 0) ans += a[y]; y = get(y , R); int val = (depth[y] - depth[x]) / c[i] + 1; ans += cnt[y][c[i]] - cnt[get(y , val * c[i])][c[i]]; } else { int R = (depth[y] - depth[x]) % c[i]; if (R > 0) ans += a[y]; y = get(y , R); while (depth[y] >= depth[x]) { ans += a[y]; y = get(y , c[i]); } } } else if (Lca == y) { if (c[i] <= MAGIC) { int val = (depth[x] - depth[y]) / c[i] + 1; ans += cnt[x][c[i]] - cnt[get(x , val * c[i])][c[i]]; } else { while (depth[x] >= depth[y]) { ans += a[x]; x = get(x , c[i]); } } } else if (c[i] <= MAGIC) { int val = (depth[x] - depth[Lca]) / c[i] + 1; ans += cnt[x][c[i]] - cnt[get(x , val * c[i])][c[i]]; int pre = get(x , (val - 1) * c[i]); int R = (depth[pre] - depth[Lca] + depth[y] - depth[Lca]) % c[i]; if (R != 0) { int now = get(y , R); val = (depth[now] - depth[Lca]) / c[i] + 1; ans += a[y] + cnt[y][c[i]] - cnt[get(y , val * c[i])][c[i]]; } else { val = (depth[y] - depth[Lca]) / c[i] + 1; ans += cnt[y][c[i]] - cnt[get(y , val * c[i])][c[i]]; if ((depth[x] - depth[Lca]) % c[i] == 0) ans -= a[Lca]; } } else { while (depth[x] >= depth[Lca]) { ans += a[x]; if (depth[x] - c[i] < depth[Lca]) break; else x = get(x , c[i]); } int R = (depth[x] - depth[Lca] + depth[y] - depth[Lca]) % c[i]; if (R != 0) { ans += a[y]; y = get(y , R); while (depth[y] >= depth[Lca]) { ans += a[y]; y = get(y , c[i]); } } else { while (depth[y] >= depth[Lca]) { ans += a[y]; y = get(y , c[i]); } if (x == Lca) ans -= a[Lca]; } } printf("%lld " , ans); } return 0; }