题解说明

问题背景：
给定一棵 $n$ 个节点的树，每个节点 $u$ 有一个限制值 $r[u]$。边有权值。题目要求计算：对于每个节点 $u$，在树上能到达的节点数（满足路径长度 $\leq r[u]$）。
代码通过 树分治 + 辅助图构建 + Tarjan 缩点 + DAG 上线段树合并 来解决。

核心思路：

1. 树分治（Centroid Decomposition）：

• 在树上找到分治中心 $rt$，递归处理。
• 对以 $rt$ 为根的子树，枚举所有节点，记录它们到 $rt$ 的距离 $depth[v]$。
• 将这些节点按深度排序，建立辅助节点链表（每个原节点对应一个辅助节点，辅助节点之间按深度相连）。

2. 辅助图构建：

• 对每个节点 $u$，找到满足 $depth[v] \leq r[u] - depth[u]$ 的最深节点 $v$，并连边 $u \to id[v]$（$id[v]$ 是辅助节点编号）。
• 每个辅助节点 $id[v]$ 再连回原节点 $v$，同时辅助节点之间形成链。
• 这样构建出的辅助图保证了“可达性”关系。

3. 强连通分量（SCC）：

• 对辅助图运行 Tarjan 算法，缩点得到 DAG。
• 每个 SCC 内的原图节点数记为 $val[i]$。

4. DAG 上的线段树合并：

• 对 DAG 进行 DFS。
• 每个 SCC 若包含原图节点，则在其线段树上打点（位置为该 SCC 的编号）。
• 合并子节点的线段树，得到当前 SCC 的可达节点集合。
• 线段树存储的是前缀和区间，支持高效合并。

5. 答案输出：

• 对于每个原图节点 $u$，找到其所在的 SCC，输出该 SCC 的线段树总和，即为 $u$ 能到达的节点数。

复杂度分析：

• 树分治：$O(n \log n)$。
• Tarjan 缩点：$O(n)$。
• DAG 上线段树合并：每个节点合并一次，复杂度 $O(n \log^2 n)$。
• 总体复杂度可控，适合 $n \leq

#include <bits/stdc++.h>
#define ll long long
#define eb emplace_back  // 简化向量插入操作
#define mk make_pair     // 简化pair创建
#define N 100009         // 基础规模定义
using namespace std;

int n, m, he[N * 20], cnt;  // he：邻接表头；cnt：边计数
vector<pair<int, ll>> V[N]; // 原图邻接表：存储{邻接点, 边权}
ll r[N];                    // 每个节点的限制值r[u]

// 辅助图的边结构
struct Edge {
    int ne, to;  // ne：下一条边；to：目标节点
} e[N * 40];

// 向辅助图添加边u->v
inline void add(int u, int v) {
    e[++cnt].ne = he[u], e[cnt].to = v, he[u] = cnt;
}

// 树分治相关变量
int sz[N], rt, mn;  // sz：子树大小；rt：当前分治中心；mn：最小子树大小的最大值
bool del[N];        // 标记节点是否已删除（用于分治）

// 寻找分治中心：在以u为根的子树中找到使最大子树最小的节点
void find(int u, int from, int n) {
    sz[u] = 1;               // 初始化当前节点子树大小为1
    int nw = 0;              // 记录最大子树大小

    for (auto x : V[u]) {    // 遍历所有邻接点
        int v = x.first;
        if (del[v] || v == from) continue;  // 跳过已删除节点或父节点

        find(v, u, n);       // 递归计算子树大小
        sz[u] += sz[v];      // 更新当前子树大小
        nw = max(nw, sz[v]); // 更新最大子树大小
    }

    nw = max(nw, n - sz[u]); // 比较父方向的子树大小

    // 更新分治中心（最小化最大子树）
    if (nw < mn) mn = nw, rt = u;
}

// 子树遍历相关变量
pair<ll, int> p[N];  // 存储{深度, 节点}对
int res, id[N * 20];  // res：节点计数；id：节点在排序后的编号
ll depth[N];          // 记录节点深度

// 遍历子树，记录所有节点的深度
void solve(int u, int from) {
    p[++res] = mk(depth[u], u);  // 记录当前节点的深度和编号

    for (auto x : V[u]) {        // 遍历所有邻接点
        int v = x.first;
        ll len = x.second;
        if (del[v] || v == from) continue;  // 跳过已删除节点或父节点

        depth[v] = depth[u] + len;  // 更新子节点深度
        solve(v, u);                // 递归遍历子树
    }
}

// 构建辅助图的边：连接满足条件的节点
void con(int u, int from) {
    // 找到最大的深度d <= r[u] - depth[u]的节点
    int pos = upper_bound(p + 1, p + res + 1, mk(r[u] - depth[u], n + 1)) - p - 1;

    if (pos)  // 若存在这样的节点，添加边u -> 该节点的排序后编号
        add(u, id[p[pos].second]);

    for (auto x : V[u]) {  // 递归处理子节点
        int v = x.first;
        if (del[v] || v == from) continue;

        con(v, u);
    }
}

// 树分治主函数：递归处理每个分治中心
void dfs(int u, int n) {
    mn = 0x3f3f3f3f;
    find(u, 0, n);       // 找到分治中心rt
    del[u = rt] = 1;     // 标记当前中心为已删除

    // 遍历当前中心的子树，记录所有节点深度
    res = 0;
    depth[u] = 0;
    solve(u, 0);

    // 按深度排序节点
    sort(p + 1, p + res + 1);

    // 为排序后的节点创建辅助节点并连接
    for (int i = 1; i <= res; i++) {
        id[p[i].second] = ++m;          // 分配辅助节点编号
        add(id[p[i].second], p[i].second);  // 辅助节点 -> 原节点

        if (i > 1)  // 辅助节点之间按排序连接（形成链）
            add(id[p[i].second], id[p[i - 1].second]);
    }

    // 为当前分治中心的所有节点添加满足条件的边
    con(u, 0);

    // 递归处理子树
    for (auto x : V[u]) {
        int v = x.first;
        if (del[v]) continue;

        dfs(v, sz[v]);  // 处理每个子树
    }
}

// Tarjan算法求强连通分量（SCC）相关变量
int dfn[N * 20], low[N * 20], stk[N * 20], top, timestamps;
int instk[N * 20], scnt, val[N * 20];  // scnt：SCC计数；val：每个SCC包含的原图节点数

// Tarjan算法：寻找强连通分量
void tarjan(int u) {
    dfn[u] = low[u] = ++timestamps;  // 初始化时间戳
    instk[u] = 1;                    // 标记入栈
    stk[++top] = u;                  // 入栈

    for (int i = he[u]; i; i = e[i].ne) {  // 遍历所有出边
        int v = e[i].to;
        if (!dfn[v]) {                     // 未访问过
            tarjan(v);
            low[u] = min(low[u], low[v]);  // 更新low值
        } else if (instk[v]) {             // 已在栈中（回边）
            low[u] = min(low[u], dfn[v]);  // 更新low值
        }
    }

    // 找到强连通分量的根
    if (dfn[u] == low[u]) {
        scnt++;
        int v;
        do {
            v = stk[top--];
            instk[v] = 0;               // 标记出栈
            id[v] = scnt;               // 记录节点所属SCC
            val[scnt] += (v <= n);      // 统计原图节点数量（v <= n为原图节点）
        } while (u != v);
    }
}

// 缩点后DAG相关变量
vector<int> E[N * 20];  // 缩点后的DAG邻接表
int vis[N * 20];        // 标记是否访问过
int rtt[N * 20], idx, S[N], idd[N * 20];  // rtt：每个SCC的线段树根；idx：线段树节点计数
                                          // S：前缀和数组；idd：SCC的排序编号

// 线段树结构：用于合并SCC的信息
struct Node {
    int l, r, sum;  // l/r：左右子树；sum：区间和
} tr[N * 400];

// 线段树上传操作
inline void pushup(int u) {
    tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
}

int lim;  // 合并时的临时限制

// 合并两个线段树（用于DAG上的信息合并）
int merge(int x, int y, int l, int r) {
    if (!x || !y || x == y) return x | y;  // 空树或同树直接返回

    // 若x覆盖整个区间，返回x
    if (tr[x].sum == S[r] - S[l - 1]) return x;
    // 若y覆盖整个区间，返回y
    if (tr[y].sum == S[r] - S[l - 1]) return y;

    if (l == r) return x;  // 叶子节点直接返回x

    // 创建新节点（复用旧节点优化内存）
    int z = x <= lim ? ++idx : x;
    int mid = (l + r) >> 1;
    // 递归合并左右子树
    tr[z].l = merge(tr[x].l, tr[y].l, l, mid);
    tr[z].r = merge(tr[x].r, tr[y].r, mid + 1, r);
    pushup(z);  // 上传结果
    return z;
}

// 线段树单点更新
void mdf(int &u, int l, int r, int d) {
    if (!u) u = ++idx;  // 新建节点

    if (l == r) {
        tr[u].sum = S[d] - S[d - 1];  // 更新叶子节点值
        return;
    }

    int mid = (l + r) >> 1;
    if (d <= mid) mdf(tr[u].l, l, mid, d);  // 更新左子树
    else mdf(tr[u].r, mid + 1, r, d);       // 更新右子树
    pushup(u);  // 上传结果
}

// 遍历DAG，合并线段树信息
void dfs(int u) {
    if (vis[u]) return;  // 已访问过直接返回
    vis[u] = 1;
    lim = idx;  // 记录当前线段树节点数（用于合并时复用）

    if (idd[u])  // 若当前SCC有编号，更新线段树
        mdf(rtt[u], 1, res, idd[u]);

    // 递归处理所有后继节点，并合并线段树
    for (auto v : E[u]) {
        dfs(v);
        rtt[u] = merge(rtt[u], rtt[v], 1, res);
    }
}

signed main() {
    // freopen("min4p.in","r",stdin);  // 调试用文件输入
    scanf("%d", &n);
    m = n;  // 辅助节点从n+1开始编号

    // 读入每个节点的r[u]
    for (int i = 1; i <= n; i++)
        scanf("%lld", &r[i]);

    // 读入边信息，构建原图
    ll z;
    for (int i = 1, x, y; i < n; i++) {
        scanf("%d%d%lld", &x, &y, &z);
        V[x].eb(mk(y, z));  // 双向边
        V[y].eb(mk(x, z));
    }

    // 树分治构建辅助图
    dfs(1, n);

    // 求辅助图的强连通分量
    for (int i = 1; i <= m; i++)
        if (!dfn[i])
            tarjan(i);

    // 构建缩点后的DAG
    for (int u = 1; u <= m; u++) {
        for (int i = he[u]; i; i = e[i].ne) {
            int v = e[i].to;
            if (id[u] != id[v])  // 不同SCC之间添加边
                E[id[u]].eb(id[v]);
        }
    }

    // 为包含原图节点的SCC分配编号并计算前缀和
    res = 0;
    for (int i = 1; i <= scnt; i++)
        if (val[i])
            S[idd[i] = ++res] = val[i];  // idd[i]：SCC的排序编号

    // 计算前缀和
    for (int i = 1; i <= res; i++)
        S[i] += S[i - 1];

    // 遍历DAG，合并线段树
    for (int i = 1; i <= scnt; i++)
        if (!vis[i])
            dfs(i);

    // 输出每个原图节点所在SCC的线段树总和（即满足条件的节点数）
    for (int i = 1; i <= n; i++)
        printf("%d ", tr[rtt[id[i]]].sum);

    return 0;
}