题意 给定一个值 s 和一棵树。在树的每个节点有一个权值，第 i 个点的权值为a[i]，问有多少条路径的节点权值总和为 s。路径中节点的深度必须是升序的。假设节点 1 是根节点，根的深度是 0，它的儿子节点的深度为 1。路径不必一定从根节点开始。 思路 路径必须是从低深度到高深度，也就是路径端点一定是祖先儿子关系，考虑倍增思路，预处理出f[i][j]：i节点的第2^ j个父亲是谁，dp[i][j]：i节点到第2^ j个父亲之间路径节点和（不包括i，包括2^j）。dfs枚举每一个节点，f[i][j] = f[f[i][j - 1]][j - 1] ；dp[i][j] = dp[i][j - 1] + dp[f[i][j - 1]][j - 1]；从i节点往上走，判断是否有路径满足和为s，用remain表示从i节点开始往上走还需要多少权值，初始化remain=s-val[i]，从大到小枚举j，如果满足remain>=dp[i][j]，则remain-=dp[i][j] , i=f[i][j]，最后判断remain是否为0即可。
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 7; typedef long long ll; int head[maxn], to[maxn<<1], nex[maxn<<1], tot; void add(int x, int y) { to[tot] = y; nex[tot] = head[x]; head[x] = tot++; } int n, s, val[maxn], ans; int f[maxn][20], dp[maxn][20]; void dfs(int x, int fx) { f[x][0] = fx;//第一个父亲就是fx dp[x][0] = val[fx];//dp[x][0]就是第一个父亲的权值 for (int i = 1; i <= 19; i++) { f[x][i] = f[f[x][i - 1]][i - 1]; dp[x][i] = dp[x][i - 1] + dp[f[x][i - 1]][i - 1]; } int now = x, remain = s - val[x]; for (int i = 19; i >= 0; i--) { if(f[now][i] && remain >= dp[now][i]) { remain -= dp[now][i]; now = f[now][i]; } } if(remain == 0) ans++; for (int i = head[x]; ~i; i = nex[i]) { int v = to[i]; if(v == fx) continue; dfs(v, x); } } int main() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &s); for (int i = 1; i <= n; i++) scanf("%d", &val[i]); for (int i = 1, x, y; i < n; i++) { scanf("%d%d", &x, &y); add(x, y); add(y, x); } dfs(1, 0); printf("%d\n", ans); }