查询从节点X开始，距离最多为D的子树中的最小权重

1. 问题描述

假设我们有一棵n个节点的树T，每个节点有一个权值w[i]，现在给定一个节点X和一个整数D，要求查询以X为根节点，距离不超过D的子树中最小的权值。

2. 解决方案

为了解决这个问题，我们可以使用深度优先搜索（DFS）和二叉搜索树（BST）的结合。具体地，我们首先使用DFS算法遍历以X为根节点的子树，然后将每个节点的权值插入到一个BST中。接下来，我们对BST进行查询，找到距离X不超过D的所有节点中权值最小的那个节点。

3. 深度优先搜索（DFS）算法

深度优先搜索（DFS）是一种经典的算法，用于遍历或搜索树、图或任何非线性数据结构。DFS从一个起始点开始，递归地访问与该点相邻的所有节点，直到所有可达节点都已被访问完毕。DFS算法的实现通常采用递归或栈的方式。

下面是使用递归方式实现DFS的C++代码实现：

void dfs(int u, int depth){
    // 处理当前节点
    // ...
    for(auto v: adj[u]){
        if(depth+1 <= D) dfs(v, depth+1);
    }
}

在上述代码中，参数u表示当前节点，参数depth表示当前节点所在的深度。adj[u]表示以u为起点的边，v表示u的下一个节点。如果u距离X的距离加上1小于等于D，则递归调用dfs(v, depth+1)。

4. 二叉搜索树（BST）

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，在BST中，左子树中所有节点的键值小于根节点的键值，右子树中所有节点的键值大于根节点的键值。BST的一个重要特点是，它支持在O(log n)的时间内查找、插入和删除节点。

下面是使用C++ STL实现BST的代码：

#include<set>
set<int> bst;
void insert(int x){
    bst.insert(x);
}
int query(int x){
    set<int>::iterator it = bst.lower_bound(x);
    if(it==bst.end()) return -1;
    return *it;
}

在上述代码中，set bst表示一个整数集合（即BST）。插入节点使用bst.insert(x)函数，查询节点使用bst.lower_bound(x)函数，它返回BST中第一个大于等于x的节点，如果不存在，则返回end()。

5. 完整代码

下面是使用DFS和BST算法解决此问题的完整C++代码：

#include<iostream>
#include<set>
#include<vector>
using namespace std;
const int N=1e5+10;
int n, X, D;
int w[N], f[N];
vector<int> adj[N];
set<int> bst;
void dfs(int u, int depth){
    insert(w[u]);
    f[u] = query(w[u])；
    for(auto v: adj[u]){
        if(depth+1 <= D) dfs(v, depth+1);
    }
    bst.erase(w[u]);
}
void insert(int x){
    bst.insert(x);
}
int query(int x){
    set<int>::iterator it = bst.lower_bound(x);
    if(it==bst.end()) return -1;
    return *it;
}
int main(){
    cin>>n>>X>>D;
    for(int i=1; i<=n; i++) cin>>w[i];
    for(int i=1, u, v; i<n; i++) {
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(X, 0);
    for(int i=1; i<=n; i++) cout<<f[i]<<' ';
    return 0;
}

6. 总结

本文介绍了如何使用深度优先搜索（DFS）和二叉搜索树（BST）的结合解决在一棵树中查找距离为D以内的子树中最小的权值的问题。我们首先使用DFS算法遍历以X为根节点的子树，然后将每个节点的权值插入到一个BST中。接下来，我们对BST进行查询，找到距离X不超过D的所有节点中权值最小的那个节点。最后，我们给出了完整的实现代码。