[NOISG2018 Finals] City Mapping 题解

· · 题解

我们大约需要一个小常数 \mathcal O(n\log n) 询问次数的做法。

我们的基本方针是维护现在的已有树，然后每次向上面在线地添加一个点，为了确保添加的这些点必然直接连接到已有树上，我们要先确定一个根，然后询问根到所有点的距离，按照距离从小到大添加。

方法一

考虑边分治的复杂度证明，如果我们每次找一个最好的边把二叉树切成两半，确定新的点加在其中的一边上，那么总的复杂度是 \mathcal O(n\log n) 的。

于是我们考虑在我们的已有树上二分。我们每次只需找到那条关键边（关键边应当满足两边的子树大小相差绝对值最小），然后确定新加入这个点在哪边就可以了。

这是简单的，考虑总有一边的子树里面有根。因为我们知道所有点到根的路径长度，我们总是可以通过一次询问确定这个点到根的路径上存不存在这条边，从而确定这个点所在的子树。

递归下去即可做到单次询问次数 \mathcal O(\log n)，总次数就是 \mathcal O(n\log n)，但是这个 \log 是非常满的，所以只能获得 74 分左右。

根据官方题解声称，此做法在随机选择树根的时候表现良好，可以获得 94 分左右。

方法二

我们考虑一个常数更小的 \log，容易想到树剖。

考虑我们每次找一条从根开始的重链，计算新加的这个点到根的路径在重链上的哪个点岔开。通过询问点到链底的距离，这是简单的。

然后把这个点的另一子树当作新的树，递归下去查询即可。如果不存在另一子树或者接在链底上就可以直接连接了。

可以发现这样每个点产生的次数是它在原树上到根的轻边数量，也就是树剖 \log，常数小到可以通过本题。

实现时需要特殊注意一下根作为三度点时的情况，此时从根上岔开的边有两种选择，不能直接递归。但是我们多使用一次询问问出在哪个就可以了。可以发现产生这种问题的点最多也只有整棵树的一半，所以无伤大雅，仍然可以通过。

std 写法好像有点丑，用了 6200 次左右通过。我写的在 5200 次左右就过了。

long long get_distance(int X, int Y);
ll rdis[N];
pll dis[N];
int rt;
vector <pii> t[N];
int siz[N];
int hson[N];
ll w[N];
vector <pll> pat;
int u;
void dfs(int x){
    siz[x]=1;
    int idx=0;
    for(auto y:t[x]){
        dfs(y.fi);
        if(siz[y.fi]>siz[idx]) idx=y.fi,w[x]=y.se;
        siz[x]+=siz[y.fi];
    }
    hson[x]=idx;
}
int route(int x,ll d){
    pat.pb(mp(x,d));
    if(hson[x]) return route(hson[x],d+w[x]);
    else return x;
}
void divide(int x){
    pat.clear();
    dfs(x);
    int bom=route(x,0);
    ll all=pat.back().se;
    ll d=get_distance(u,bom);
    fr1(i,0,(int)pat.size()-1){
        if(d+all-2*(all-pat[i].se)==rdis[u]-rdis[x]){
            int id=pat[i].fi;
            ll w=rdis[u]-rdis[id];
            if(t[id].size()>=2){
                if(pat[i+1].fi==t[id][0].fi) swap(t[id][0],t[id][1]);
                if(id==1){
                    if(t[id].size()==3) if(pat[i+1].fi==t[id][1].fi) swap(t[id][1],t[id][2]);
                    ll td0=get_distance(t[id][0].fi,u);
                    if(rdis[u]==td0+t[id][0].se) divide(t[id][0].fi);
                    else{
                        if(t[id].size()==3) divide(t[id][1].fi);    
                        else t[id].pb(mp(u,w));
                    }
                    return;
                }
                divide(t[id][0].fi);
                return;
            }
            else{
                t[id].pb(mp(u,w));
                return;
            }
        }
    }
}
void find_roads(int n, int Q, int A[], int B[], int W[]){
    rt=1;
    fr1(i,2,n) rdis[i]=dis[i].fi=get_distance(rt,i),dis[i].se=i;
    sort(dis+2,dis+n+1);
    fr1(i,2,n){
        u=dis[i].se;
        divide(1);
    }
    int tot=-1;
    fr1(i,1,n){
        for(auto y:t[i]){
            tot++;
            A[tot]=i,B[tot]=y.fi,W[tot]=y.se;
        }
    }
}