题目链接

题意

一开始已知一号点。
每次可以选定一个已知点和一个未知点，然后交互库会返回从已知点出发到达未知点路径上的第二个点。
要求在有限步之内知道每一个点。

次数要求:
链的情况要求 \(O(n)\)
其余是 \(O(nlogn)\)

Sol

首先是链的情况，记录当前左右端点不断往后探索即可。
然后是树，初始想法肯定就是不断迭代，最坏情况是 \(O(n^2)\) 的。

我们的瓶颈在于如果树的深度比较大，我们迭代的时候来回走了很多个圈就不好处理。
那么我们很容易想到用点分树来优化我们迭代的过程。
于是动态维护点分树即可。
每次新加一个点的时候直接加入，向上更新点分树祖先的 \(size\) ，设定一个平衡因子，当当前子树大小过大时就把当前子树暴力重构一下。记录每一个点在点分树中的深度就很好做了。

code:

#include<bits/stdc++.h>
#include "rts.h"
using namespace std;
const int N=3e5+10;
namespace TP3{
    int n;int lnow,rnow;bool del[N];int S[N];
    void work(int _n){
        n=_n;
        lnow=rnow=1;for(int i=1;i<n;++i) S[i]=i+1;del[1]=1;
        srand(time(NULL));random_shuffle(S+1,S+n);
        for(int i=1;i<n;++i){
            int now=lnow;bool f=0;
            while(!del[S[i]]) {
                int v=explore(now,S[i]);
                if(del[v]) now=rnow,f=1;
                else {
                    del[v]=1;now=v;
                    if(f==0) lnow=now;
                    else rnow=now;
                }
            }
            if(rand()&1) swap(lnow,rnow);
        }
        return;
    }
}
namespace Sol{
    int n;
    typedef double db;
    const db alpha=0.7;
    struct edge{int to,next;}a[N<<1];
    int head[N],cnt=0;
    inline void add(int x,int y){a[++cnt]=(edge){y,head[x]};head[x]=cnt;}
    int fa[N],vis[N],size[N],f[N],que[N],had[N],mark[N],sz[N],dep[N];
    int rt;int now,SZ,RT,UP;
    void Find(int u,int fr){
        sz[u]=1,f[u]=0;
        for(int v,i=head[u];i;i=a[i].next){
            v=a[i].to;if(v==fr||vis[v]) continue;
            Find(v,u);sz[u]+=sz[v];
            f[u]=max(f[u],sz[v]);
        }
        f[u]=max(f[u],SZ-sz[u]);
        if(!RT||(f[u]<f[RT])) RT=u;
    }
    void Build(int u,int fr){
        fa[u]=fr;size[u]=1;dep[u]=dep[fr]+1;vis[u]=1;
        for(int v,i=head[u];i;i=a[i].next){
            v=a[i].to;if(dep[v]<UP||vis[v]) continue;
            RT=0;SZ=sz[v];Find(v,u);
            int To=RT;Build(To,u);
            size[u]+=size[To];
        }
        return;
    }
    void Clear(int u,int fa){
        vis[u]=0,mark[u]=0;
        for(int v,i=head[u];i;i=a[i].next){v=a[i].to;if(v==fa||dep[v]<UP) continue;Clear(v,u);}
        return;
    }
    inline void Rebuild(int u){// 重构子树
        SZ=size[u];UP=dep[u];RT=0;
        Clear(u,0);Find(u,0);if(rt==u) rt=RT;
        Build(RT,fa[u]);
        return;
    }
    void Maintain(int u){// 向上更新点分树 size 并判断重构
        if(!fa[u]) {if(mark[u]) Rebuild(u);return;}
        ++size[fa[u]];
        if(size[fa[u]]*alpha<size[u]) mark[fa[u]]=1;
        Maintain(fa[u]);
        if(mark[u]) Rebuild(u);// 找到最上面需要重构的点
        return;
    }
    void work(int _n){
        n=_n;
        for(int i=1;i<n;++i) que[i]=i+1;
        srand(time(NULL));
        random_shuffle(que+1,que+n);
        had[1]=size[1]=vis[1]=rt=1,dep[1]=1;
        int tot=1;
        for(int i=1;i<n;++i) {
            now=rt;
            while(!had[que[i]]){
                int p=explore(now,que[i]);
                if(had[p]) {
                    while(now!=fa[p]) p=fa[p];now=p;
                }
                else {
                    ++tot;had[p]=1;
                    add(now,p),add(p,now);
                    fa[p]=now,size[p]=1,vis[p]=1,dep[p]=dep[now]+1;
                    Maintain(p);now=p;
                }
            }
        }
    }
}
void play(int n, int T, int dataType) {
    if(dataType==3) TP3::work(n);
    else Sol::work(n);
}

【UOJ#349】[WC2018] 即时战略

原文：https://www.cnblogs.com/NeosKnight/p/10500729.html