洛谷-P11315 [RMI 2021] 速通 / Speedrun 题解

Solution注意到100021010002^{10}1000210也就是每个节点恰好能存两个≤n\le n≤n的整数。无根树不好考虑先钦定111为根转化成有根树。首先每个点可以先记一个父亲这样就可以一路跳到根解决了不知道出发点的问题。我们只需要在记一下每个点uuu的 dfs 序后继nxtunxt_unxtu​。不断尝试走向nxtunxt_unxtu​失败了就跳父亲接着试。因为我们从根开始 dfs每问111次就走111步一共2N−22N-22N−2步因此试错次数2N2N2N可以通过。Code#includespeedrun.h#includebits/stdc.h#definerep(i,a,b)for(inti(a);ib;i)#definerept(i,a,b)for(inti(a);ib;i)#defineebemplace_backusingnamespacestd;constexprintMAXN1e35;vectorintg[MAXN];intlst;voidsetNum(intu,intk,intx){rep(i,0,10)setHint(u,k*10i1,xi1);}intgetNum(intk){intres0;rep(i,0,10)res|int(getHint(k*10i1))i;returnres;}voiddfs(intu,intpre){setNum(u,0,pre);if(lst)setNum(lst,1,u);lstu;for(intv:g[u])if(v^pre)dfs(v,u);}voidassignHints(intsubtask,intN,intA[],intB[]){setHintLen(20);rept(i,1,N)g[i].clear();rep(i,1,N)g[A[i]].eb(B[i]),g[B[i]].eb(A[i]);dfs(1,0);}voidspeedrun(intsubtask,intN,intstart){assert(getLength()20);intt;while(tgetNum(0))goTo(t);while(tgetNum(1))while(!goTo(t))goTo(getNum(0));}