【题解】CF#983 E-NN country

　　首先，我们从 u -> v 有一个明显的贪心，即能向上跳的时候尽量向深度最浅的节点跳。这个我们可以用树上倍增来维护。我们可以认为 u 贪心向上跳后不超过 lca 能跳到 u' 的位置， v 跳到 v' 的位置，这时只需要查询一下是否有 u' -> v' 的直达公交线路就可以确定出答案了。

　　如果 u 和 v 在一条链上，我们可以直接倍增获得答案，所以以下讨论均为 u != lca && v != lca 的情况。若在节点 u 和 v 之间存在一条直达线路，说明有一条线路的起点在以 u 为根的子树内，重点在以 v 为根的子树内。即起点的dfs序 >= dfn[u] && <= dfn[u] + size[u] - 1, 终点的 dfs序 >= dfn[v] && <= dfn[v] + size[v] -1;这是一个二维限制的问题，暴力主席树就可以搞定……

　　之后看题解发现其实有一种妙妙的做法并不需要主席树。我们可以离线处理。要查询是否有起点在 u 的子树内且终点在 v 的子树内的路线，就是dfs在进入 u 的子树内之前记录下 v 的子树内此时记录的路径数，然后进入子树，遇到路线则标记终点所在的位置。返回之后两相对比，如果此时 v 的子树内记录的路径数有增长的话说明这样的路线是存在的。

#include <bits/stdc++.h>

using namespace std;

#define maxn 450000

#define INF 99999999

#define CNST 20

int n, m, q, Mul[maxn][CNST], gra[maxn][CNST];

int dfn[maxn], dep[maxn], bits[];

int tot, timer, root[maxn], fa[maxn], size[maxn];

int read()

{

    int x = , k = ;

    char c; c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

struct edge

{

    int cnp, to[maxn], last[maxn], head[maxn];

    edge() { cnp = ; }

    void add(int u, int v)

    { to[cnp] = v, last[cnp] = head[u], head[u] = cnp ++; }

}E1, G;

struct edge1

{

    int u, v;

    edge1(int _u = , int _v = ) { u = _u, v = _v; }

    friend bool operator <(const edge1& a, const edge1& b)

    { return (dfn[a.u] != dfn[b.u]) ? dfn[a.u] < dfn[b.u] : dfn[a.v] < dfn[b.v]; }

}e[maxn];

struct node

{

    int u, num;

    node(int _u = , int _num = )

    { u = _u, num = _num; }

};

struct node1

{

    int sum, ls, rs;

}T[maxn * ];

void dfs(int u)

{

    gra[u][] = fa[u], dfn[u] = ++ timer; size[u] = ;

    for(int i = ; i < CNST; i ++) gra[u][i] = gra[gra[u][i - ]][i - ];

    for(int i = E1.head[u]; i; i = E1.last[i])

    {

        int v = E1.to[i];

        dep[v] = dep[u] + ; dfs(v);

        size[u] += size[v];

    }

}

int dfs2(int u)

{

    int lim = ;

    for(int i = G.head[u]; i; i = G.last[i])

    {

        if(u != G.to[i]) lim = (dep[lim] < dep[G.to[i]]) ? lim : G.to[i];

        if(!lim && u != G.to[i]) lim = G.to[i];

    }

    for(int i = E1.head[u]; i; i = E1.last[i])

    {

        int v = E1.to[i];

        int t = dfs2(v);

        if(u != t && t) lim = (dep[lim] < dep[t]) ? lim : t;

        if(!lim && u != t) lim = t;

    }

    Mul[u][] = lim;

    return lim;

}

void dfs3(int u)

{

    for(int i = ; i < CNST; i ++)

        Mul[u][i] = Mul[Mul[u][i - ]][i - ];

    for(int i = E1.head[u]; i; i = E1.last[i])

        dfs3(E1.to[i]);

}

int LCA(int u, int v)

{

    if(dep[u] < dep[v]) swap(u, v);

    for(int i = CNST - ; ~i; i --)

        if(dep[gra[u][i]] >= dep[v]) u = gra[u][i];

    for(int i = CNST - ; ~i; i --)

        if(gra[u][i] != gra[v][i]) u = gra[u][i], v = gra[v][i];

    return (u == v) ? u : gra[u][];

}

node Jump(int u, int fu)

{

    bool flag = ; int cnt = ;

    if(dep[u] == dep[fu]) flag = ;

    for(int i = CNST - ; ~i; i --)

    {

        if(!Mul[u][i]) continue;

        if(dep[Mul[u][i]] <= dep[fu]) flag = ;

        if(dep[Mul[u][i]] > dep[fu]) u = Mul[u][i], cnt += bits[i];

    }

    if(!flag) return node(-, );

    else return node(u, cnt);

}

void Ins(int &now, int pre, int l, int r, int x)

{

    now = ++ tot; T[now] = T[pre]; T[now].sum ++;

    if(l == r) return;

    int mid = (l + r) >> ;

    if(x <= mid) Ins(T[now].ls, T[pre].ls, l, mid, x);

    else Ins(T[now].rs, T[pre].rs, mid + , r, x);

}

bool Query(int now, int pre, int l, int r, int L, int R)

{

    if(!now) return ;

    if(L == l && R == r) return (T[now].sum - T[pre].sum);

    if(L > r || R < l) return ;

    int mid = (l + r) >> ;

    if(R <= mid) return Query(T[now].ls, T[pre].ls, l, mid, L, R);

    else if(L > mid) return Query(T[now].rs, T[pre].rs, mid + , r, L, R);

    else

    {

        if(Query(T[now].ls, T[pre].ls, l, mid, L, mid)) return ;

        else return Query(T[now].rs, T[pre].rs, mid + , r, mid + , R);

    }

}

int main()

{

    n = read();

    bits[] = ; for(int i = ; i < CNST; i ++) bits[i] = bits[i - ] << ;

    for(int i = ; i <= n; i ++)

    {

        fa[i] = read();

        E1.add(fa[i], i);

    }

    dep[] = ; dfs();

    m = read();

    for(int i = ; i <= m; i ++)

    {

        int u = read(), v = read(), lca = LCA(u, v);

        G.add(u, lca); G.add(v, lca);

        e[i] = edge1(u, v);

    }

    dfs2(); dfs3();

    sort(e + , e +  + m); int last = ; root[] = tot = ;

    for(int i = ; i <= m; i ++)

    {

        while(last < dfn[e[i].u] - ) T[root[last + ] = ++ tot] = T[root[last]], last ++;

        Ins(root[dfn[e[i].u]], root[last], , n, dfn[e[i].v]);

        if(last != dfn[e[i].u]) last ++;

    }

    while(last +  <= n) T[root[last + ] = ++ tot] = T[root[last]], last ++;

    q = read();

    for(int i = ; i <= q; i ++)

    {

        int u = read(), v = read(), lca = LCA(u, v);

        node a = Jump(u, lca), b = Jump(v, lca);

        int fu = a.u, fv = b.u;

        if(fu == - || fv == -) { printf("-1\n"); continue; }

        if(u == lca || v == lca) { printf("%d\n", a.num + b.num + ); continue; }

        int l1 = dfn[fu], r1 = dfn[fu] + size[fu] - ;

        int l2 = dfn[fv], r2 = dfn[fv] + size[fv] - ;

        int x = Query(root[r1], root[l1 - ], , n, l2, r2);

        int y = Query(root[r2], root[l2 - ], , n, l1, r1);

        printf("%d\n", a.num + b.num +  + !(x || y));

    }

    return ;

}

巴特西

【题解】CF#983 E-NN country

最新文章

热门文章