集邮 5 / Collecting Stamps 5 JOI Final 2026

[JOI Final 2026] 集邮 5 / Collecting Stamps 5

淀粉质好题！

[JOI Final 2026] 集邮 5 / Collecting Stamps 5。

给定 nn 个点的树，第 ii 个点点权为 aia_i。

给定常数 DD，试对于每一个 ii，求出满足以下条件的 jj 的个数：

  • 提取出 i,ji,j 路径上的所有点，依次排开为 p0,p1,⋯ ,pmp_0,p_1,\cdots,p_m，其中 p0=i,pm=jp_0=i,p_m=j；
  • 存在一个 0≤x≤m0\le x\le m，使得 dist(i,px)≥apx\text{dist}(i,p_x)\ge a_{p_x}。

n≤4×105n\le 4\times 10^5，0≤D≤n0\le D\le n，0≤ai≤n0\le a_i\le n。

子任务 1：n≤3000n\le 3000；

子任务 2：D=n−1D=n-1。

对于子任务 1，只需要枚举每个点 dfs 即可。

然后重点关注子任务 2。

首先对于 x,yx,y 以及其路径上的 p0,p1,⋯ ,pmp_0,p_1,\cdots,p_m 中的某一个 pip_i，其满足条件当且仅当 dist(x,pi)≥api\text{dist}(x,p_i)\ge a_{p_i}，我们不妨将式子变形：

dist(x,pi)≥apidx+dpi−2dlca(x,pi)≥apiapi−dpi≤dx−2dlca(x,pi)\text{dist}(x,p_i)\ge a_{p_i}\\ d_x+d_{p_i}-2d_{\text{lca}(x,p_i)}\ge a_{p_i}\\ a_{p_i}-d_{p_i}\le d_x-2d_{\text{lca}(x,p_i)}

既然转化成了含有最近公共祖先的式子，就不难考虑到点分治。

设 l=lca(x,y)l=\text{lca}(x,y)，那么所有 x,yx,y 路径上的点可以分为两类：位于 x,lx,l 路径上，以及位于 l,yl,y 路径上。

将这两种分别处理可以得到两种限制条件：

  • x,lx,l 路径上：api+dpi≤dxa_{p_i}+d_{p_i}\le d_x；
  • l,yl,y 路径上：api−dpi≤dx−2dla_{p_i}-d_{p_i}\le d_x-2d_l。

那么我们不妨设点分治中心为 ll，那么每次根据 ll 去计算分治子树的深度 dd，这样 dl=0d_l=0。

于是限制就变为了 api+dpi≤dxa_{p_i}+d_{p_i}\le d_x 和 api−dpi≤dxa_{p_i}-d_{p_i}\le d_x。

然后问题突然就变成了简单的点分治基础题目，枚举 xx 即可。没什么细节，不过多赘述。只需要一个树状数组统计前缀和即可。

子任务 2 就被解决了。

接着看有 DD 的限制的情况。可以发现其实就是多了一维偏序限制，可持久化线段树即可。

实现细节

Part I.

关于可持久化线段树的实现，没什么好说的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int ls[M],rs[M],num[M],R[N],idx,md,c[N],ID;
vector<int>V[N];
void copy(int x,int y){ls[x]=ls[y],rs[x]=rs[y],num[x]=num[y];}
int build(int p,int l,int r){
    p=++idx;
    if(l==r)return p;
    int mid=(l+r)>>1;
    ls[p]=build(p,l,mid);
    rs[p]=build(p,mid+1,r);
    return p;
}
int insert(int p,int l,int r,int x,int y){
    ++idx,copy(idx,p),p=idx;
    if(l==r){
        num[p]+=y;
        return p;
    }
    int mid=(l+r)>>1;
    if(mid>=x)ls[p]=insert(ls[p],l,mid,x,y);
    else rs[p]=insert(rs[p],mid+1,r,x,y);
    num[p]=num[ls[p]]+num[rs[p]];
    return p;
}
int query(int p,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return num[p];
    int mid=(l+r)>>1,res=0;
    if(mid>=ql)res+=query(ls[p],l,mid,ql,qr);
    if(mid<qr)res+=query(rs[p],mid+1,r,ql,qr);
    return res;
}
int rnk(int x,int y){return x<0?0:query(R[min(md+1,x+1)],0,n,0,y);}

Part II.

点分治的最最基础的部分，没什么好说的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int n,D,a[N],ans[N];
vector<int>v[N];
int sz[N],F[N],S,rt,st[N];
#define err cerr<<"Running on line: "<<__LINE__<<". "
#define out cout<<"Running on line: "<<__LINE__<<". "
void getrt(int x,int fa){
    sz[x]=1;
    F[x]=0;
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        getrt(u,x);
        sz[x]+=sz[u];
        F[x]=max(F[x],sz[u]);
    }
    F[x]=max(F[x],S-sz[x]);
    if(F[x]<F[rt])rt=x;
}
int dep[N];
1
2
3
4
5
6
7
8
9
10
void solve(int x){
    st[x]=1;
    //do something.
    for(int u:v[x]){
        if(st[u])continue;
        S=sz[u],rt=0;
        getrt(u,0),getrt(rt,0);
        solve(rt);
    }
}

Part III.

主函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main(){
    F[0]=1e9;
    scanf("%d%d",&n,&D);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    R[0]=build(1,0,n);
    ID=idx;
    S=n,rt=0;
    getrt(1,0),getrt(rt,0);
    solve(rt);
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}

Part IV.

统计答案（不含容斥）。

首先先看 solve 函数的内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve(int x){
    //...
    md=0;
    dfs(x,0,0,n+1);
    for(int i=0;i<=md;i++){
        R[i+1]=R[i];
        for(int u:V[i])
            R[i+1]=insert(R[i+1],0,n,max(u,0),1);
    }
    for(int i=1;i<=md;i++)c[i]+=c[i-1];
    for(int u:v[x]){
        if(st[u])continue;
        dfs2(u,x,a[x]+dep[x]);
    }
    ans[x]+=rnk(D,0);
    for(int i=0;i<=md;i++)c[i]=0;
    for(int i=ID+1;i<=idx;i++)
        ls[i]=rs[i]=num[i]=0;
    for(int i=0;i<=md;i++)V[i].clear();
    idx=ID;
    //...
}

首先明确定义：

  • mdmd 表示最大深度；
  • VV 用来存储所有要进入可持久化线段树的点；
  • stst 是点分治中不能去的点；
  • depdep 是以 xx 为根的分治子树的深度；
  • cc 表示深度 ≤x\le x 的点的个数

然后看 dfs 函数：

1
2
3
4
5
6
7
8
9
10
11
void dfs(int x,int fa,int dis,int minn){
    minn=min(minn,a[x]-dis);
    dep[x]=dis;
    md=max(md,dep[x]);
    c[dep[x]]++;
    V[dep[x]].push_back(minn);
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        dfs(u,x,dis+1,minn);
    }
}

其作用显然：

  • 更新 md,dis,c,Vmd,dis,c,V；

注意这里有一个取 min⁡\min 的操作，原因是因为只要路径上有一个数能满足条件，这个数就满足条件。

而由于我们的限制都是形如 ≤dx\le d_x 的，如果把 xx 看作常量，那么很显然只要 min⁡\min 能达到，这个点就能达到。

然后是 dfs2 函数，其作用是统计所有点的答案。

1
2
3
4
5
6
7
8
9
void dfs2(int x,int fa,int minn){
    minn=min(minn,a[x]+dep[x]);
    if(minn<=dep[x])ans[x]+=dep[x]>D?0:c[min(md,D-dep[x])];
    else ans[x]+=rnk(D-dep[x],dep[x]);
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        dfs2(u,x,minn);
    }
}

那么 if 分支是为了判断：x,lx,l 路径上是否有满足条件的点。

如果有，那么所有满足深度条件的点都能成为答案。

否则，只要满足第二个条件的点才能成为答案。

因此，应该使用 if 分类讨论。

solve 函数最后的就是清空了。

Part V.

接下来是容斥的部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve(int x){
    //...
    for(int u:v[x]){
        if(st[u])continue;
        md=0;
        dfs3(u,x,a[x]-dep[x]);
        for(int i=0;i<=md;i++){
            R[i+1]=R[i];
            for(int u:V[i])
                R[i+1]=insert(R[i+1],0,n,max(u,0),1);
        }
        for(int i=1;i<=md;i++)c[i]+=c[i-1];
        dfs4(u,x,a[x]+dep[x]);
        for(int i=0;i<=md;i++)c[i]=0;
        for(int i=ID+1;i<=idx;i++)
            ls[i]=rs[i]=num[i]=0;
        for(int i=0;i<=md;i++)V[i].clear();
        idx=ID;
    }
    //...
}

这里大部分都和刚才的一样，只不过这里是针对子树：要容斥掉子树内的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs3(int x,int fa,int minn){
    minn=min(minn,a[x]-dep[x]);
    md=max(md,dep[x]);
    c[dep[x]]++;
    V[dep[x]].push_back(minn);
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        dfs3(u,x,minn);
    }
}
void dfs4(int x,int fa,int minn){
    minn=min(minn,a[x]+dep[x]);
    if(minn<=dep[x])ans[x]-=dep[x]>D?0:c[min(md,D-dep[x])];
    else ans[x]-=rnk(D-dep[x],dep[x]);
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        dfs4(u,x,minn);
    }
}

Code

非常好的题目！建议先从子任务 2 的树状数组开始打。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>
using namespace std;
const int N=400010,M=10000010;
int n,D,a[N],ans[N];
vector<int>v[N];
int sz[N],F[N],S,rt,st[N];
#define err cerr<<"Running on line: "<<__LINE__<<". "
#define out cout<<"Running on line: "<<__LINE__<<". "
void getrt(int x,int fa){
    sz[x]=1;
    F[x]=0;
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        getrt(u,x);
        sz[x]+=sz[u];
        F[x]=max(F[x],sz[u]);
    }
    F[x]=max(F[x],S-sz[x]);
    if(F[x]<F[rt])rt=x;
}
int dep[N];
int ls[M],rs[M],num[M],R[N],idx,md,c[N],ID;
vector<int>V[N];
void copy(int x,int y){ls[x]=ls[y],rs[x]=rs[y],num[x]=num[y];}
int build(int p,int l,int r){
    p=++idx;
    if(l==r)return p;
    int mid=(l+r)>>1;
    ls[p]=build(p,l,mid);
    rs[p]=build(p,mid+1,r);
    return p;
}
int insert(int p,int l,int r,int x,int y){
    ++idx,copy(idx,p),p=idx;
    if(l==r){
        num[p]+=y;
        return p;
    }
    int mid=(l+r)>>1;
    if(mid>=x)ls[p]=insert(ls[p],l,mid,x,y);
    else rs[p]=insert(rs[p],mid+1,r,x,y);
    num[p]=num[ls[p]]+num[rs[p]];
    return p;
}
int query(int p,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return num[p];
    int mid=(l+r)>>1,res=0;
    if(mid>=ql)res+=query(ls[p],l,mid,ql,qr);
    if(mid<qr)res+=query(rs[p],mid+1,r,ql,qr);
    return res;
}
int rnk(int x,int y){return x<0?0:query(R[min(md+1,x+1)],0,n,0,y);}
void dfs(int x,int fa,int dis,int minn){
    minn=min(minn,a[x]-dis);
    dep[x]=dis;
    md=max(md,dep[x]);
    c[dep[x]]++;
    V[dep[x]].push_back(minn);
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        dfs(u,x,dis+1,minn);
    }
}
void dfs2(int x,int fa,int minn){
    minn=min(minn,a[x]+dep[x]);
    if(minn<=dep[x])ans[x]+=dep[x]>D?0:c[min(md,D-dep[x])];
    else ans[x]+=rnk(D-dep[x],dep[x]);
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        dfs2(u,x,minn);
    }
}
void dfs3(int x,int fa,int minn){
    minn=min(minn,a[x]-dep[x]);
    md=max(md,dep[x]);
    c[dep[x]]++;
    V[dep[x]].push_back(minn);
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        dfs3(u,x,minn);
    }
}
void dfs4(int x,int fa,int minn){
    minn=min(minn,a[x]+dep[x]);
    if(minn<=dep[x])ans[x]-=dep[x]>D?0:c[min(md,D-dep[x])];
    else ans[x]-=rnk(D-dep[x],dep[x]);
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        dfs4(u,x,minn);
    }
}
void solve(int x){
    st[x]=1;
    md=0;
    dfs(x,0,0,n+1);
    for(int i=0;i<=md;i++){
        R[i+1]=R[i];
        for(int u:V[i])
            R[i+1]=insert(R[i+1],0,n,max(u,0),1);
    }
    for(int i=1;i<=md;i++)c[i]+=c[i-1];
    for(int u:v[x]){
        if(st[u])continue;
        dfs2(u,x,a[x]+dep[x]);
    }
    ans[x]+=rnk(D,0);
    for(int i=0;i<=md;i++)c[i]=0;
    for(int i=ID+1;i<=idx;i++)
        ls[i]=rs[i]=num[i]=0;
    for(int i=0;i<=md;i++)V[i].clear();
    idx=ID;
    for(int u:v[x]){
        if(st[u])continue;
        md=0;
        dfs3(u,x,a[x]-dep[x]);
        for(int i=0;i<=md;i++){
            R[i+1]=R[i];
            for(int u:V[i])
                R[i+1]=insert(R[i+1],0,n,max(u,0),1);
        }
        for(int i=1;i<=md;i++)c[i]+=c[i-1];
        dfs4(u,x,a[x]+dep[x]);
        for(int i=0;i<=md;i++)c[i]=0;
        for(int i=ID+1;i<=idx;i++)
            ls[i]=rs[i]=num[i]=0;
        for(int i=0;i<=md;i++)V[i].clear();
        idx=ID;
    }
    for(int u:v[x]){
        if(st[u])continue;
        S=sz[u],rt=0;
        getrt(u,0),getrt(rt,0);
        solve(rt);
    }
}
int main(){
    F[0]=1e9;
    scanf("%d%d",&n,&D);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    R[0]=build(1,0,n);
    ID=idx;
    S=n,rt=0;
    getrt(1,0),getrt(rt,0);
    solve(rt);
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}

注意需要卡常，如果可以，建议换成树状数组扫描线。

附上树状数组扫描线代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
using namespace std;
const int N=400010;
using pii=pair<int,int>;
int n,D,a[N],ans[N];
vector<int>v[N];
int sz[N],F[N],S,rt,st[N];
void getrt(int x,int fa){
    sz[x]=1;
    F[x]=0;
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        getrt(u,x);
        sz[x]+=sz[u];
        F[x]=max(F[x],sz[u]);
    }
    F[x]=max(F[x],S-sz[x]);
    if(F[x]<F[rt])rt=x;
}
int dep[N],md,c[N],C[N];
void add(int x,int y){for(int i=x+1;i<=n+1;i+=i&-i)C[i]+=y;}
int query(int x,int cnt=0){for(int i=x+1;i>=1;i-=i&-i)cnt+=C[i];return cnt;}
vector<int>V[N];
vector<pii>Q[N];
void dfs(int x,int fa,int dis,int minn){
    minn=min(minn,a[x]-dis);
    dep[x]=dis;
    md=max(md,dep[x]);
    c[dep[x]]++;
    V[dep[x]].push_back(max(0,minn));
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        dfs(u,x,dis+1,minn);
    }
}
void dfs2(int x,int fa,int minn){
    minn=min(minn,a[x]+dep[x]);
    if(minn<=dep[x])ans[x]+=dep[x]>D?0:c[min(md,D-dep[x])];
    else if(dep[x]<=D)Q[min(md,D-dep[x])].push_back({dep[x],x});
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        dfs2(u,x,minn);
    }
}
void dfs3(int x,int fa,int minn){
    minn=min(minn,a[x]-dep[x]);
    md=max(md,dep[x]);
    c[dep[x]]++;
    V[dep[x]].push_back(max(0,minn));
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        dfs3(u,x,minn);
    }
}
void dfs4(int x,int fa,int minn){
    minn=min(minn,a[x]+dep[x]);
    if(minn<=dep[x])ans[x]-=dep[x]>D?0:c[min(md,D-dep[x])];
    else if(dep[x]<=D)Q[min(md,D-dep[x])].push_back({dep[x],x});
    for(int u:v[x]){
        if(u==fa||st[u])continue;
        dfs4(u,x,minn);
    }
}
void solve(int x){
    st[x]=1;
    md=0;
    dfs(x,0,0,n+1);
    for(int i=1;i<=md;i++)c[i]+=c[i-1];
    for(int u:v[x]){
        if(st[u])continue;
        dfs2(u,x,a[x]+dep[x]);
    }
    Q[min(D,md)].push_back({0,x});
    for(int i=0;i<=md;i++){
        for(int u:V[i])add(u,1);
        for(pii u:Q[i])ans[u.second]+=query(u.first);
    }
    for(int i=0;i<=md;i++)c[i]=0;
    for(int i=0;i<=md;i++)for(int j:V[i])add(j,-1);
    for(int i=0;i<=md;i++)V[i].clear(),Q[i].clear();
    for(int u:v[x]){
        if(st[u])continue;
        md=0;
        dfs3(u,x,a[x]-dep[x]);
        for(int i=1;i<=md;i++)c[i]+=c[i-1];
        dfs4(u,x,a[x]+dep[x]);
        for(int i=0;i<=md;i++){
            for(int u:V[i])add(u,1);
            for(pii u:Q[i])ans[u.second]-=query(u.first);
        }
        for(int i=0;i<=md;i++)c[i]=0;
        for(int i=0;i<=md;i++)for(int j:V[i])add(j,-1);
        for(int i=0;i<=md;i++)V[i].clear(),Q[i].clear();
    }
    for(int u:v[x]){
        if(st[u])continue;
        S=sz[u],rt=0;
        getrt(u,0),getrt(rt,0);
        solve(rt);
    }
}
int main(){
    F[0]=1e9;
    scanf("%d%d",&n,&D);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    S=n,rt=0;
    getrt(1,0),getrt(rt,0);
    solve(rt);
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}