树分治 NOI 2026 贪心二分

传送 NOI 2026 实现细节

WZH2026-08-062026-08-06

[NOI 2026] 传送实现细节

上篇题解是口胡的，写完代码后感觉有点细节。

代码结构：

using ll=long long;
using pli=pair<ll,int>;
using V=vector<int>;
ll gcd(ll a,ll b); // 最大公约数
struct Q{}; // 有理数结构体
namespace DFT{ // 点分树
    int Min(int x,int y); // dfn-lca 比较函数
    void dfs(int x,int fa); // dfn-lca 预处理函数
    int lca(int x,int y); // dfn-lca 实现函数
    int dist(int x,int y); // 距离函数
    void getrt(int x,int fa); // 找重心
    void dfs2(int x,int fa,int aim,int c[],ll res[],int &mx); // 对于每个分治重心，预处理距离
    void solve(int x); // 点分治
    pli query(int x,int k); // 找距离 x 不超过 k 的点个数 (second) 和距离和 (first)
    Q cost(int x,int k); // 当距离 x 超过 k 的点选传送，其他点选向 x 移动时，选传送的点期望秒数
    void build(V &ur,V &vr); // DFT 预处理函数
    Q get_tele_ans(int x,int y); // 询问的函数
}
vector<pli>teleport(int c,int n,int m,V ur,V vr,V xr,V yr); // 交互函数

Part I 交互函数

vector<pli>teleport(int c,int n,int m,V ur,V vr,V xr,V yr);

DFT 已经提供好了所有函数，模拟就行。

vector<pli>teleport(int c,int n,int m,V ur,V vr,V xr,V yr){
    for(int i=0;i<n-1;i++)ur[i]++,vr[i]++;
    for(int i=0;i<m;i++)xr[i]++,yr[i]++;
    DFT::build(ur,vr);
    vector<pli>ans(m);
    for(int i=0;i<m;i++){
        Q t=DFT::get_tele_ans(xr[i],yr[i]);
        ans[i]={t.a,t.b};
    }
    return ans;
}

Part II 有理数结构体

ll gcd(ll a,ll b);

struct Q{};

可以直接模拟分数四则运算。不过要注意，为了保证性能，可以在所有运算结束后最后约分。

ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
struct Q{
    ll a,b;
    Q():a(0),b(1){}
    Q(ll x):a(x),b(1){}
    Q(ll a,ll b):a(a),b(b){}
    Q operator+(Q x){return Q(a*x.b+b*x.a,b*x.b);}
    Q operator-(Q x){return Q(a*x.b-b*x.a,b*x.b);}
    Q operator*(Q x){return Q(a*x.a,b*x.b);}
    Q operator/(Q x){return Q(a*x.b,b*x.a);}
    bool operator<=(const Q &x)const{return a*x.b<=b*x.a;}
    void easy(){
        ll t=gcd(a,b);
        a/=t,b/=t;
    }
};

Part III dfn-lca

int Min(int x,int y);

void dfs(int x,int fa);

int lca(int x,int y);

int dist(int x,int y);

经典 dfn-lca ，可以利用 RMQ 做到 $\mathcal{O}(n\log n)\sim\mathcal{O}(1)$ 或 $\mathcal{O}(n)\sim\mathcal{O}(1)$ 。

namespace DFT{
    int Min(int x,int y){return d[x]<d[y]?x:y;}
    void dfs(int x,int fa){
        dfn[x]=++id;
        St[0][id]=fa;
        d[x]=d[fa]+1;
        for(int u:v[x]){
            if(u==fa)continue;
            dfs(u,x);
        }
    }
    int lca(int x,int y){
        if(x==y)return x;
        if(dfn[x]>dfn[y])swap(x,y);
        int l=dfn[x]+1,r=dfn[y],k=lg[r-l+1];
        return Min(St[k][l],St[k][r-(1<<k)+1]);
    }
    int dist(int x,int y){return d[x]+d[y]-2*d[lca(x,y)];}
}

Part IV 找重心

getrt(int x,int fa);

板子。

namespace DFT{
    int rt,F[N],sz[N],S;
    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;
    }
}

Part V 点分治

void dfs2(int x,int fa,int aim,int c[],ll res[],int &mx);

void solve(int x);

我们的目标是处理树上 $k$ 邻域数点。

回顾一下过程，我们需要处理出每一个分治重心 $x$ 的分治子树内所有点到 $x$ 的距离，以及 $x$ 的分治子树内到 $x$ 分治父亲 $f$ 的距离，以及距离和。

处理完后，我们需要把这些信息放在桶里并统计前缀和。

以上与点分树 / 震波是一致的。

但是，考虑到每个分治重心 $x$ 的分治子树内距离最远的点到 $x$ 距离互不相同。

考虑到这题 $n\le5\times10^5$ ，所以我们不能向震波一样使用常数巨大的 vector ，而应该使用类似于长链剖分的指针。

具体的，定义 c[] 和 c2[] 分别代表距离 $x$ 不超过 $k$ 的点个数， res[] 和 res2[] 分别代表距离 $x$ 不超过 $k$ 的点距离和。

然后，定义 addr[] 和 ed[] 代表 $x$ 的桶在 c[] 和 res[] 中的范围，定义 addr2[] 和 ed2[] 代表 $x$ 的桶在 c2[] 和 res2[] 中的范围。

这样就可以成功规避 vector 。

其他的和震波别无二致。

namespace DFT{
    int addr[N],Ad,c[M],mx,ed[N],f[N];
    int addr2[N],Ad2,c2[M],mx2,ed2[N];
    ll res[N],res2[N];
    void dfs2(int x,int fa,int aim,int c[],ll res[],int &mx){
        int t=dist(x,aim);
        mx=max(mx,t);
        c[t]++;res[t]+=t;
        for(int u:v[x]){
            if(u==fa||st[u])continue;
            dfs2(u,x,aim,c,res,mx);
        }
    }
    void solve(int x){
        st[x]=1;
        mx=0;mx2=0;
        addr[x]=Ad;addr2[x]=Ad2;
        dfs2(x,0,x,c+addr[x],res+addr[x],mx);
        if(f[x])dfs2(x,0,f[x],c2+addr2[x],res2+addr2[x],mx2);
        ed[x]=Ad+mx,ed2[x]=Ad2+mx2;
        Ad=ed[x]+1,Ad2=ed2[x]+1;
        for(int i=addr[x]+1;i<=ed[x];i++)
            c[i]+=c[i-1],res[i]+=res[i-1];
        for(int i=addr2[x]+1;i<=ed2[x];i++)
            c2[i]+=c2[i-1],res2[i]+=res2[i-1];
        for(int u:v[x]){
            if(st[u])continue;
            S=sz[u];rt=0;
            getrt(u,0);getrt(rt,0);
            f[rt]=x;g[x].push_back(rt);
            solve(rt);
        }
    }
}

Part VI query(x,k)

query(int x,int k);

这个函数和震波里的那个没什么区别。

就是经典树上 $k$ 邻域数点的查询。

不过要注意边界问题。

namespace DFT{
    pli query(int x,int k){
        ll ans1=res[min(addr[x]+k,ed[x])];
        int ans2=c[min(addr[x]+k,ed[x])];
        int t=x,p=1;
        while(f[t]){
            int y=k-dis[x][p];
            if(y>=0){
                ans1+=res[min(addr[f[t]]+y,ed[f[t]])]+dis[x][p]*c[min(addr[f[t]]+y,ed[f[t]])];
                ans1-=res2[min(addr2[t]+y,ed2[t])]+dis[x][p]*c2[min(addr2[t]+y,ed2[t])];
                ans2+=c[min(addr[f[t]]+y,ed[f[t]])];
                ans2-=c2[min(addr2[t]+y,ed2[t])];
            }
            t=f[t],p++;
        }
        return {ans1,ans2};
    }
}

Part VII cost(x,k)

cost(int x,int k);

推一下公式即可。

不妨定义 $S$ 为期望， $y$ 为距离 $x$ 不超过 $k$ 的点个数， $Y$ 为距离 $x$ 不超过 $k$ 的点到 $x$ 的距离和。

那么就有 $S=1+\frac{n-y}{n}S+\frac{y}{n}Y$ 。

解得 $S=\frac{n+Y}{y}$ 。

namespace DFT{
    Q cost(int x,int k){
        pli t=query(x,k);
        return Q(n+t.first,t.second);
    }
}

Part VIII get_tele_ans(x,y)

get_tele_ans(int x,int y);

设 $E[p]$ 为节点 $p$ 作为终点时，选择随机传送的点的最低期望。

那么直接返回 $\min\{d(x,y),E[y]\}$ 就行。

namespace DFT{
    Q E[N];
    Q get_tele_ans(int x,int y){
        Q T1=dist(x,y),T2=E[y];
        return T1<=T2?T1:T2;
    }
}

Part IX 初始化点分树

build(V &ur,V &vr);

首先，我们要根据 ur 和 vr 建边。

然后，我们要调用 dfs 初始化 lca 。

接着，我们要用 solve 建立点分树。

之后，我们要初始化 dis[i][p] 表示 $i$ 的点分树上的 $p$ 级父亲和 $i$ 的距离。

最后，我们要用 cost 二分最优的 E[] 。

namespace DFT{
        void build(V &ur,V &vr){
        F[0]=1e9;
        n=ur.size();
        for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
        for(int i=0;i<n-1;i++){
            v[ur[i]].push_back(vr[i]);
            v[vr[i]].push_back(ur[i]);
        }
        dfs(1,0);
        for(int i=1;i<=19;i++)
            for(int j=1;j+(1<<i)-1<=n;j++)
                St[i][j]=Min(St[i-1][j],St[i-1][j+(1<<i-1)]);
        S=n;getrt(1,0);getrt(rt,0);solve(rt);
        for(int i=1;i<=n;i++){
            int t=i,p=0;
            while(t){   
                dis[i][p]=dist(i,t);
                t=f[t],p++;
            }
        }
        // for(int i=1;i<=n;i++){
        //     for(int j=0;j<n;j++)cout<<cost(i,j).a<<' '<<cost(i,j).b<<" ; ";
        //     cout<<"\n";
        // }
        for(int i=0;i<=n;i++){
            int l=0,r=n-1;
            while(l<r){
                int mid=(l+r)>>1;
                if(cost(i,mid)<=Q(mid+1))r=mid;
                else l=mid+1;
            }
            E[i]=cost(i,l);E[i].easy();
          //  cout<<E[i].a<<'/'<<E[i].b<<"\n";
        }
    }
}

然后就 $\mathcal{O}(n\log^2n)$ 通过此题。