题解：P15947 [JOI Final 2026] 集邮 5 / Collecting Stamps 5
DSD486
·
·
题解
简洁 \mathcal{O}(n \log n) 做法。
我说很简单但我考上不想写点分治你信吗。
显然点分治。
考虑一条路径 s \longrightarrow rt \longrightarrow t。
其中 rt 是分治中心。
分讨 a_u 在哪边：
- 在 s \longrightarrow rt 上。
因为 u 在 s 往上走的路上，所以耗时是 dep_s - dep_u。
触发条件是 dep_s - dep_u \ge a_u \iff dep_s \ge a_u + dep_u。
限制了这个条件后另一边的 t 任选。
- 在 rt \longrightarrow t 上。
那么触发条件是 $dep_s + dep_u \ge a_u \iff dep_s \ge a_u - dep_u$。
---
注意到这两部分独立，所以从分治中心往下走处理每个 $s$ 到 $rt$ 的路径上的 $\min(a_u + dep_u)$，能得出这边有没有 $a_u$ 合法。
顺便能处理出 $\min(a_u - dep_u)$ 表示另一边合法的限制。
+ 如果 $s$ 上半段已经合法，即要求 $dep_s \in [0, m - dep_t]$。
+ 如果 $s$ 上半段没合法，即要求 $dep_s \in [s[t], m - dep_t]$。
对于每个 $t$ 给的区间做差分单点加，因为是深度限制，所以事实上不用前缀和到 $m$，做完了。
::::success[Code]
```cpp
#include <bits/stdc++.h>
//#define int long long
#define PII pair < int , int >
#define x first
#define y second
using namespace std ;
bool bbb ;
const int N = 4e5 + 5 , inf = 1e9 ;
int n , m , a[N] ;
vector < int > g[N] ;
int sz[N] , vis[N] ;
int dp[N] , rt ;
void getsz(int u , int fa){
sz[u] = 1 ;
for(int v : g[u]) if(v != fa && !vis[v])
getsz(v , u) , sz[u] += sz[v] ;
}
void getrt(int u , int fa , int tot){
dp[u] = 0 ;
for(int v : g[u]) if(v != fa && !vis[v])
getrt(v , u , tot) , dp[u] = max(dp[u] , sz[v]) ;
dp[u] = max(dp[u] , tot - sz[u]) ;
if(dp[rt] > dp[u]) rt = u ;
}
int dep[N] , hf[N] , s[N] ;
vector < int > p ;
void getd(int u , int fa , int v1 , int v2 , int w){ // v1 : a[u] + dep[u] , v2 : a[u] - dep[u]
dep[u] = dep[fa] + 1 ;
if(w == 1){
v1 = min(v1 , a[u] + dep[u]) , v2 = min(v2 , max(0 , a[u] - dep[u])) ;
hf[u] = v1 <= dep[u] , s[u] = v2 ;
}
p.push_back(u) ;
for(int v : g[u]) if(v != fa && !vis[v])
getd(v , u , v1 , v2 , w) ;
}
int cf[N][2] ;
long long ans[N] ;
void calc(int u , int d , int w){
dep[0] = d , getd(u , 0 , inf , inf , w) ;
int mx = 0 ;
for(int i : p) mx = max(mx , dep[i]) ;
int lim = min(m , mx) ;
for(int i : p){
int r = min(lim , m - dep[i]) + 1 ;
if(m >= dep[i] && r > 0)
++ cf[0][1] , -- cf[r][1] ;
if(m - dep[i] >= s[i] && r > s[i])
++ cf[s[i]][0] , -- cf[r][0] ;
}
for(int i = 1 ; i <= lim ; i++)
cf[i][0] += cf[i - 1][0] ,
cf[i][1] += cf[i - 1][1] ;
for(int i : p)
if(dep[i] <= lim)
ans[i] += 1ll * cf[dep[i]][hf[i]] * w ;
for(int i = 0 ; i <= lim + 1 ; i++)
cf[i][0] = cf[i][1] = 0 ;
p.clear() ;
}
void solve(int u){
calc(u , -1 , 1) , vis[u] = 1 ;
for(int v : g[u]) if(!vis[v])
calc(v , 0 , -1) ,
rt = 0 , getsz(v , u) , getrt(v , u , sz[v]) , solve(rt) ;
}
bool eee ;
signed main(){
// freopen("distort.in" , "r" , stdin) ;
// freopen("distort.out" , "w" , stdout) ;
ios :: sync_with_stdio(0) ;
cin.tie(0) ; cout.tie(0) ;
cerr << "Memory: " << abs((char*)&eee - (char*)&bbb) / 1024.0 / 1024.0 << " MB\n" ;
cin >> n >> m ;
for(int i = 1 ; i <= n ; i++) cin >> a[i] ;
for(int i = 1 , u , v ; i < n ; i++){
cin >> u >> v ;
g[u].push_back(v) ,
g[v].push_back(u) ;
}
dp[rt = 0] = inf , getsz(1 , 0) , getrt(1 , 0 , n) , solve(rt) ;
for(int i = 1 ; i <= n ; i++) cout << ans[i] << '\n' ;
return 0 ;
}
/*
```
::::