本文共 2120 字，大约阅读时间需要 7 分钟。

   
  
   
  
   
  
题意
  
   
  
给出以1号点为根的一棵有根树，问每个点的子树中与它距离小于等于l的点有多少个。
  
   
  
题解
  
   
  
这道题目要求我们计算一棵有根树中每个节点的子树中，距离该节点不超过l的节点个数。解决这个问题可以通过并查集（Union-Find）数据结构结合深度优先搜索（DFS）来实现。
  
   
  
首先，我们需要对树进行深度优先搜索（DFS），计算每个节点的深度。然后，我们使用并查集来维护当前处理的子树的代表节点，并根据距离限制将节点归类到不同的集合中。通过这种方法，我们可以高效地计算每个节点的符合条件的子树节点数量。
  
   
  
具体来说，我们使用并查集来维护每个节点的代表节点（代表树的根节点），并根据节点的深度来决定是否将其归类到当前节点所在的集合中。这样可以确保每个节点的子树中距离其不超过l的节点都被计算在内。
  
   
  
最后，我们通过深度优先搜索遍历所有节点，并根据并查集的结果计算每个节点的子树中满足条件的节点数量。
  
   
  
代码解释
  
   
  
以下是实现上述算法的C++代码：
  
   
  
```pre  
#include 
   
      
#include 
    
       
#include 
     
        
using namespace std;  
typedef long long LL;  
const LL N = 200005;  
LL n, l;  
struct qq {  
    LL x, y, z, last;  
};  
LL num, last[N];  
LL ans[N];  
LL dep[N];  
LL s1[N], s2[N];  
LL v[N], c[N];  
LL rt[N];  
LL d[N];  
void init(LL x, LL y, LL z) {  
    num++;  
    e[num].x = x;  
    e[num].y = y;  
    e[num].z = z;  
    e[num].last = last[x];  
    last[x] = num;  
}  
LL bt(LL x) {  
    v[++num] = x;  
    c[num] = 1;  
    s1[num] = s2[num] = d[num] = 0;  
    return num;  
}  
LL Merge(LL x, LL y) {  
    if (x == 0 || y == 0) return x + y;  
    if (v[x] < v[y]) swap(x, y);  
    s2[x] = Merge(s2[x], s2[y]);  
    c[x] = c[s1[x]] + c[s2[x]] + 1;  
    if (d[s2[x]] > d[s1[x]]) swap(s1[x], s2[x]);  
    d[x] = d[s2[x]] + 1;  
    return x;  
}  
void dfs(LL x) {  
    rt[x] = bt(dep[x]);  
    for (LL u = last[x]; u != -1; u = e[u].last) {  
        LL y = e[u].y;  
        dep[y] = dep[x] + e[u].z;  
        dfs(y);  
        rt[x] = Merge(rt[x], rt[y]);  
        while (v[rt[x]] > dep[x] + l) {  
            rt[x] = Merge(s1[rt[x]], s2[rt[x]]);  
        }  
    }  
    ans[x] = c[rt[x]];  
}  
int main() {  
    num = 0;  
    memset(last, -1, sizeof(last));  
    scanf("%lld%lld", &n, &l);  
    for (LL u = 2; u <= n; u++) {  
        LL x, z;  
        scanf("%lld%lld", &x, &z);  
        init(x, u, z);  
    }  
    num = 0;  
    dep[1] = 1;  
    dfs(1);  
    for (LL u = 1; u <= n; u++) {  
        printf("%lld\n", ans[u]);  
    }  
    return 0;  
}
     
    
   

该代码通过并查集和深度优先搜索的结合方式，实现了对树结构的高效处理。通过合并操作，我们能够有效地维护当前处理的子树的代表节点，并根据节点的深度来决定是否将其归类到当前节点所在的集合中。最终，我们可以计算出每个节点的子树中距离其不超过l的节点数量。

转载地址：http://facq.baihongyu.com/