up on 1.14：感谢 Jordan_Pan 指出【取到答案下界的证明】有误，已加以修正。（快关注 Jordan_Pan 喵，千粉女装喵）

前置知识

最近公共祖先，虚树。

简要题意

给定 $n$ 个节点的树，点有点权。求最小的路径条数，使得未被任何一条路径覆盖的点的点权最大值与最小值之差小于等于 $D$。

思路分析

看到极差小于等于 $D$，套路地枚举未被覆盖点的点权最小值，点权最大值不降，按点权排序后双指针。

然后问题等价于给定一个点集，支持增删点，求最小可重叠路径覆盖。

容易得到答案下界是这些点构成的虚树的叶子节点数除二向上取整（因为每次操作至多消去两个叶子节点）。

证明可以考虑数学归纳法：每颗树可以被考虑为逐步增加叶子节点得到，记叶子节点数为 $s$。当 $s=1$ 或者 $s=2$ 时，显然成立；当 $s \gt 3$ 时，如果 $s-1$ 为偶数，则可以视为在 $s-1$ 答案的基础上多加入了一条链，结论成立。如果 $s-1$ 为奇数，则取出之前最后加入的三个叶子节点，将这四点两两组合，总有一种组合能覆盖这两条路径的并，所以答案等于 $s-1$ 的答案，结论成立。

然后将点集中的点按 dfn 排序后形成序列 p，特判只有一个叶子节点的情况，其余情况叶子节点数就是 $\sum_{i=1}^{n-1}([\operatorname{lca}(p_i,p_{i+1}) \ne p_i][\operatorname{lca}(p_i,p_{i+1}) \ne p_{i+1}])+[\operatorname{lca}_{i \in [1,n]}\{p_i\}=p_1][\operatorname{lcaz}(p_2,z) \ne \operatorname{lcaz}(p_n,z)]+1$，其中 $\operatorname{lcaz}(x,y)$ 表示 $y$ 在 $x$ 方向的儿子。

第一个求和式中 $p_i,p_{i+1}$ 产生贡献等价于 $p_i,p_{i+1}$ 不存在祖先关系。

第二个式子产生贡献等价于虚树的根节点在点集中并且度数为 $1$。

上式的总意义是考虑正常 dfs 的过程中一次回溯并继续递归会贡献一个叶子节点，然后在算上第一个被递归到的叶子节点并且特判虚树根节点是否为叶子。

时间复杂度 $O(n \log n)$。

代码实现得一坨（，精细实现应该很快。

代码

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#define FOR(i,a,b) for(int i = (a);i <= (b);++i)
#define REP(i,a,b) for(int i = (a);i >= (b);--i)
#define GO(x) for(int i = h[x],y = e[i];i;y = e[i=ne[i]])
#define ve std::vector
static char stkk[200];
template<typename T>inline void output(T x){
    if(!x)return putchar('0'),void();
    if(x<0)x = ~x+1,putchar('-');
    int top = 0;
    for(;x;stkk[++top]=x%10^48,x/=10);
    for(;top;putchar(stkk[top--]));
}
template<typename T>inline void readx(T &x){
    x = 0;int y = 1;char c = getchar();
    for(;c<48||c>58;c = getchar())if(c=='-')y = -1;
    for(;c>=48&&c<=58;c = getchar())x = (x<<1)+(x<<3)+(c^48);
    x *= y;
}
inline void ckmin(int &x,int y){
    x>y&&(x=y);
}
const int N = 2e5+10;
static int v[N];
static int e[N<<1],ne[N<<1],h[N],T;
inline void add(int x,int y){
    e[++T] = y,ne[T] = h[x],h[x] = T;
}
static int p[N],dfn[N],nfd[N],dfsct,dep[N],sz[N],sn[N],tp[N],fa[N];
static int tmp,p0,tot;
void dfs0(int x,int fr){
    nfd[dfn[x]=++dfsct] = x;
    sz[x] = 1,dep[x] = dep[fa[x]=fr]+1;
    int ct = 0;
    GO(x)if(y^fr){
        dfs0(y,x),++ct,sz[x]+=sz[y];
        if(sz[sn[x]]<sz[y])sn[x] = y;
    }
    if(!ct)++tmp;
    if(!fr&&ct<=1)++p0;
}
void dfs1(int x,int tt){
    if(!x)return;
    tp[x] = tt;
    dfs1(sn[x],tt);
    GO(x)if(y^sn[x]&&y^fa[x])dfs1(y,y);
}
inline int get_min(int x,int y){
    return dep[x]<dep[y]?x:y;
}
inline int lca(int x,int y){
    for(;tp[x]!=tp[y];x = fa[tp[x]])if(dep[tp[x]]<dep[tp[y]])std::swap(x,y);
    return get_min(x,y);
}
inline int lca_z(int x,int z){
    int pre = -1;
    for(;tp[x]!=tp[z];x = fa[pre=tp[x]]);
    return x==z?pre:sn[z];
}
inline int cal(int x,int y){
    return lca(x,y)!=get_min(x,y);
}
std::multiset<int> s;
inline void get(int x,int &pre,int &nxt){
    auto tmp = s.lower_bound(dfn[x]);
    if(tmp!=s.end())nxt = *tmp;
    else nxt = *s.begin();
    if(tmp!=s.begin())pre = *prev(tmp);
    else pre = *prev(s.end());
    pre = nfd[pre],nxt = nfd[nxt];
}
inline void add_x(int x){
    int pre,nxt;
    get(x,pre,nxt);
    tmp+=cal(pre,x)+cal(x,nxt)-cal(pre,nxt);
    s.insert(dfn[x]),++tot;
}
inline void del_x(int x){
    s.erase(s.find(dfn[x])),--tot;
    int pre,nxt;
    get(x,pre,nxt);
    tmp-=cal(pre,x)+cal(x,nxt)-cal(pre,nxt);
}
inline int f(int d){
    return tot==1?1:(tmp+d+1)/2;
}
int pre[N],suf[N];
int solve(int n,int D,ve<int> C,ve<int> P,ve<int> Q){
    //rd
    FOR(i,1,n)v[i] = C[i-1];
    FOR(i,0,n-2)++P[i],++Q[i],add(P[i],Q[i]),add(Q[i],P[i]);
    //dfs0
    dfs0(1,0),--tmp,dfs1(1,1);
    //init and sort p,for i,j,get_ans
    FOR(i,1,n)p[i] = i;
    std::sort(p+1,p+1+n,[&](int x,int y){return v[x]!=v[y]?v[x]<v[y]:dfn[x]<dfn[y];});
    int ans;
    if(v[p[n]]-v[p[1]]<=D)ans = 0;
    else{
        ans = n==1?1:(tmp+1+p0+1)/2;
        pre[1] = p[1],suf[n] = p[n];
        FOR(i,2,n)pre[i] = lca(p[i],pre[i-1]);
        REP(i,n-1,1)suf[i] = lca(p[i],suf[i+1]);
        FOR(i,1,n)s.insert(i);tot = n;
        for(int i = 1,j = 1;i <= n;add_x(p[i++])){
            for(;j<=n&&v[p[j]]<=v[p[i]]+D;del_x(p[j++]));
            int z = i==1?suf[j]:j>n?pre[i-1]:lca(pre[i-1],suf[j]);
            if(z==0)puts("Err"),exit(0);
            int d = tot==1?0:(tot!=1)+(nfd[*s.begin()]==z&&lca_z(nfd[*next(s.begin())],z)==lca_z(nfd[*prev(s.end())],z))-cal(nfd[*s.begin()],nfd[*prev(s.end())]);
            ckmin(ans,f(d));
        }
    }
    //output
    return ans;
}