题解：P15947 [JOI Final 2026] 集邮 5 / Collecting Stamps 5

· · 题解

蛤？什么叫我当时打线上赛的时候觉得这题难完了。

统计路径，使用点分治。设当前分治中心为 rt，称从时刻 0 出发走 u\to rt 能被拍到时为上向边，称 rt\to u 能被拍到时为下向边。所有上向边本身对 u 的贡献和下向边对 rt 的贡献直接顺手算。若 a_{rt}=0，原地结束也算一种。

接下来考虑一条路径 u\to rt\to v 拼接的情况。记 d_x=\operatorname{dis}(rt,x)，设 d=d_u。

把这个式子和总长度限制放在一起。对于一个固定的 v，它能贡献的起点深度恰好是

\min_{x\in rt\leadsto v}(a_x-d_x)\le d\le m-d_v.

左端点 DFS 的时候顺手维护。上向边也一样，走 u\to rt 到 x 时的时间是 d-d_x，所以只要维护路径上的 \min(a_x+d_x)，看它是否 \le d。

于是开三棵树状数组。第一棵按深度存所有终点，第二棵只存下向边的终点，第三棵对剩下的终点把上面的区间加一。起点是上向边就查第一棵的前缀，否则查第二棵的前缀，再加上第三棵在 d 处的值。

按儿子分枝扫，先查完整条分枝再加入，就不会算到同一分枝里的路径（也就是不容斥）。这样只能查到前面的分枝，倒着再扫一遍就行。以 rt 为端点的贡献只算一次，同一分枝里的路径留给递归。

时间复杂度 O(n\log^2 n)，空间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
#define uint int32_t
#define mkp make_pair
const int N=4e5+5;
int n,m,a[N],siz[N],vis[N],nowsiz,rt,mx[N];
vector <int> e[N];
struct BIT{
    int c[N];
    void add(int x,int y){x++;
        for(;x<=n+1;x+=x&(-x))c[x]+=y;
    }
    int calc(int x){
        if(x<0)return 0;
        int ans = 0;x++;
        for(;x;x-=x&(-x))ans+=c[x];
        return ans;
    }
    void clear(int x){x++;
        for(;x<=n+1;x+=x&(-x))c[x]=0;
    }
}tr,tr1,tr2,tr3;
void getrt(int u,int fa){
    siz[u]=1,mx[u]=0;
    for(auto v:e[u]){
        if(v==fa||vis[v])continue;
        getrt(v,u);siz[u]+=siz[v];
        mx[u]=max(mx[u],siz[v]);
    }mx[u]=max(mx[u],nowsiz-siz[u]);
    if(mx[rt]>mx[u])rt=u;
}
int len,len1,maxdis,sz,dis[N];
struct Point{
    int u,d,op,dt;
}p[N],s[N];
void dfs1(int u,int fa,int d1,int v1,int v2,int f1,int f2){
    if(d1>m)return;
    v1=min(v1,a[u]+d1);
    v2=min(v2,a[u]-d1);
    if(v1<=d1)f1=1;
    if(d1>=a[u])f2=1;
    p[++len]=(Point){u,d1,f1,0};
    s[++len1]=(Point){u,v2,f2,d1};
    for(auto v:e[u]){
        if(v==fa||vis[v])continue;
        dfs1(v,u,d1+1,v1,v2,f1,f2);
    }
}//no problem
int col[N],ans[N];
void dfs3(int u,int fa,int d1){
    tr1.clear(d1),tr2.clear(d1);
    for(auto v:e[u]){
        if(v==fa||vis[v])continue;
        dfs3(v,u,d1+1);
    }
}
inline void calc(int u){int lst = 0,cnt1=0;len=len1=0;sz=maxdis=0;
    dis[u]=0;
    for(int i = 0;i < e[u].size();i++){
        int v = e[u][i];
        if(vis[v])continue;
        dfs1(v,u,1,a[u],a[u],(a[u]==0),(a[u]==0));
        for(int j = lst+1;j <= len;j++){
            if(p[j].op){//上向边 
                ans[p[j].u]++;//u->rt,已经计入了
                ans[p[j].u]+=tr1.calc(m-p[j].d);//之前的所有边 
            }else{
                ans[p[j].u]+=tr2.calc(m-p[j].d);//向下边条数
                ans[p[j].u]+=tr3.calc(p[j].d);
                //拼接 
            } 
        }
        for(int j = lst+1;j <= len1;j++){
            if(!s[j].op){
                int l = s[j].d,r = m-s[j].dt;
                if(l<=r)tr3.add(l,1),tr3.add(r+1,-1);
            }else tr2.add(s[j].dt,1);tr1.add(s[j].dt,1);
        }lst=len;
    }ans[u]+=tr2.calc(m);
    //向下边对rt的贡献。
    if(!a[u])ans[u]++;
    //此时a[u]=0还没有被计算，它只作为确定状态参与子树点的状态计算 
    //dfs3(u,0,0);
    for(int i = 1;i <= len;i++)tr1.clear(p[i].d),tr2.clear(p[i].d);
    for(int i = 1;i <= len1;i++){
        if(!s[i].op){
            int l = s[i].d,r = m-s[i].dt;
            if(l<=r)tr3.clear(l),tr3.clear(r+1);
        }
    }
    lst = 0,sz=0,cnt1=0;len=len1=0;maxdis=0;
    for(int i = e[u].size()-1;i >= 0;i--){
        int v = e[u][i];
        if(vis[v])continue;
        dfs1(v,u,1,a[u],a[u],(a[u]==0),(a[u]==0));
        for(int j = lst+1;j <= len;j++){
            if(p[j].op){//上向边 
                ans[p[j].u]+=tr1.calc(m-p[j].d);
            }else{
                ans[p[j].u]+=tr2.calc(m-p[j].d);
                ans[p[j].u]+=tr3.calc(p[j].d);
                //拼接 
            } 
        }
        for(int j = lst+1;j <= len1;j++){
            if(!s[j].op){
                int l = s[j].d,r = m-s[j].dt;
                if(l<=r)tr3.add(l,1),tr3.add(r+1,-1);
            }else tr2.add(s[j].dt,1);tr1.add(s[j].dt,1);
        }lst=len;
    }
    for(int i = 1;i <= len;i++)tr1.clear(p[i].d),tr2.clear(p[i].d);
    for(int i = 1;i <= len1;i++){
        if(!s[i].op){
            int l = s[i].d,r = m-s[i].dt;
            if(l<=r)tr3.clear(l),tr3.clear(r+1);
        }
    }
}
void dfs(int u){
    vis[u]=1,calc(u);int lst = nowsiz;
    for(auto v:e[u]){
        if(vis[v])continue;
        rt=0,nowsiz=(siz[u]>siz[v]?siz[v]:lst-siz[u]);
        getrt(v,u),dfs(rt);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;mx[0]=n+1;
    for(int i = 1;i <= n;i++)cin >> a[i];
    for(int i = 1,u,v;i < n;i++){
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }nowsiz=n;getrt(1,0);dfs(rt);
    for(int i = 1;i <= n;i++)cout << ans[i] << "\n";
    return 0;
}