题解：P17141 [NOI 2026] 传送（暂无数据）

· · 题解

对于任意局面，无论从任何节点使用传送门，其后的期望步数是一定的。因此局面固定时，一个点的答案就是直接走到 y，或者走到最近的传送位置传送，二者较小值。那你发现，钦定完要走到 y 的点后，把剩下的点全都设作传送点是不劣的。

钦定走到 y 的点必然是一个连续段，我们记段内点数为 c、到 y 距离和为 s，则走随机的期望步数 E 满足：

E=1+\frac{s}{n}+\frac{n-c}{n}E\implies E=\frac{n+s}{c}

你注意到任意调整单点使其到根期望步数减小，E 不增，故而调整完的局面必然形如，与 y 距离不超过 lim=\lfloor E\rfloor 的直接走 y，剩下的走随机。我们发现 E 关于 lim 是单谷，故而可以对每个 y 二分找到最终的 lim，复杂度 O(n^2+m)。

瓶颈在于对每个 y 找 c,s 序列，树上邻域问题考虑点分树，复杂度 O(n\log^2n+m)。大常数选手原地爆炸。

你发现不用对每个 y 都二分，当 y 从一个点 a 移动到其相邻点 b 时，E 变化不超过 1，从而 lim 变化也不超过 1，故而我们对根节点二分之后对其余点只需进行 O(n) 次查询，复杂度 O(n\log n+m)。

const int N=5e5+5,T=19;

int n,m;
vec<int> g[N];

pll e[N];
il bool chk(pll a,pll b){return a.fir*b.sec>b.fir*a.sec;}//a>b
int dcnt,dfn[N],to[N],st[N][T],fa[N],dp[N],lg[N];
void dfs0(int x){
    dfn[x]=++dcnt,to[dcnt]=x;st[dcnt][0]=fa[x],dp[x]=dp[fa[x]]+1;
    for(auto y:g[x])if(y!=fa[x])fa[y]=x,dfs0(y);
}
il int dis(int a,int b){
    if(a==b)return 0;
    int res=dp[a]+dp[b];
    a=dfn[a],b=dfn[b];if(a>b)swap(a,b);
    int t=lg[b-a];++a;
    int c=dp[st[a][t]]<dp[st[b-(1<<t)+1][t]]?st[a][t]:st[b-(1<<t)+1][t];
    return res-dp[c]-dp[c];
}

bool don[N];
int sz[N],mx[N],siz,rt;
int th[N],h[N],Fa[N],dh[N];
vec<ll> c[N],s[N],dc[N],ds[N];
void gsiz(int x,int fa){
    sz[x]=1;
    for(auto y:g[x])if(!don[y]&&y!=fa)gsiz(y,x),sz[x]+=sz[y];
}
void grot(int x,int fa){
    mx[x]=siz-sz[x];
    for(auto y:g[x])if(!don[y]&&y!=fa)grot(y,x),chmax(mx[x],sz[y]);
    if(mx[x]<mx[rt])rt=x;
}
void dfs1(int x,int fa,int &h){
    chmax(h,th[x]);
    for(auto y:g[x])if(!don[y]&&y!=fa)th[y]=th[x]+1,dfs1(y,x,h);
}
void dfs2(int x,int fa,vec<ll> &c,vec<ll> &s){
    c[th[x]]++,s[th[x]]+=th[x];
    for(auto y:g[x])if(!don[y]&&y!=fa)dfs2(y,x,c,s);
}
int build(int x,int f){
    int r=x;
    gsiz(x,0),siz=sz[x],mx[rt=0]=inf,grot(x,0),x=rt;
    th[x]=0,dfs1(x,0,h[x]);
    c[x].resize(h[x]+1),s[x].resize(h[x]+1);
    dfs2(x,0,c[x],s[x]);
    rep(i,1,h[x])c[x][i]+=c[x][i-1],s[x][i]+=s[x][i-1];
    Fa[x]=f;
    th[r]=1,dfs1(r,0,dh[x]);
    dc[x].resize(dh[x]+1),ds[x].resize(dh[x]+1);
    dfs2(r,0,dc[x],ds[x]);
    rep(i,1,dh[x])dc[x][i]+=dc[x][i-1],ds[x][i]+=ds[x][i-1];
    don[x]=1;for(auto y:g[x])if(!don[y])build(y,x);
    return x;
}
pll getv(int x,int d){
    int st=x,sd=d;
    ll rc=c[x][min(d,h[x])],rs=s[x][min(d,h[x])];
    while(Fa[x]){
        int dt=dis(st,Fa[x]);d=sd-dt;
        if(d<0){x=Fa[x];continue;}
        rc-=dc[x][min(d,dh[x])],rs-=ds[x][min(d,dh[x])]+dc[x][min(d,dh[x])]*dt;
        x=Fa[x];
        rc+=c[x][min(d,h[x])],rs+=s[x][min(d,h[x])]+c[x][min(d,h[x])]*dt;
    }
    return {rc,rs};
}

int ch[N];
void dfs3(int x,int fa){
    if(fa){
        e[x]={inf,1};ll c,s;
        if(ch[fa]>0)tie(c,s)=getv(x,ch[fa]-1),chk(e[x],{n+s,c})&&(e[x]={n+s,c},ch[x]=ch[fa]-1);
        tie(c,s)=getv(x,ch[fa]),chk(e[x],{n+s,c})&&(e[x]={n+s,c},ch[x]=ch[fa]);
        if(ch[fa]<n-1)tie(c,s)=getv(x,ch[fa]+1),chk(e[x],{n+s,c})&&(e[x]={n+s,c},ch[x]=ch[fa]+1);
    }
    for(auto y:g[x])if(y!=fa)dfs3(y,x);
}

vec<pli> teleport(int cc,int nn,int mm,vec<int> u,vec<int> v,vec<int> x,vec<int> y){
    n=nn,m=mm;
    repl(i,1,n)++u[i-1],++v[i-1],g[u[i-1]].pub(v[i-1]),g[v[i-1]].pub(u[i-1]);
    dfs0(1);
    rep(i,2,n)lg[i]=lg[i>>1]+1;
    repl(t,1,T)rep(i,1,n-(1<<t)+1)st[i][t]=dp[st[i][t-1]]<dp[st[i+(1<<t-1)][t-1]]?st[i][t-1]:st[i+(1<<t-1)][t-1];
    build(1,0);
    int l=0,r=n-1;
    while(l<r){
        int m1=l+r>>1;int m2=m1+1;
        auto [c1,s1]=getv(1,m1);auto [c2,s2]=getv(1,m2);
        if(chk({n+s1,c1},{n+s2,c2}))l=m1+1;else r=m1;
    }
    auto [c,s]=getv(1,ch[1]=l);
    e[1]={n+s,c};
    dfs3(1,0);
    vec<pli> res(m);
    repl(i,0,m){
        ++x[i],++y[i];
        pll t={dis(x[i],y[i]),1};
        t=chk(e[y[i]],t)?t:e[y[i]];
        ll g=__gcd(t.fir,t.sec);
        t.fir/=g,t.sec/=g;
        res[i]=t;
    }
    return res;
}