你基环树森林找直径都是中等, lca咋还简单呢

题面

给定一个n个顶点的有向图，每个顶点有且仅有一条出边。

对于顶点i，记它的出边为(i, a[i])。

再给出q组询问，每组询问由两个顶点a、b组成，要求输出满足下面条件的x、y：

从顶点a沿着出边走x步和从顶点b沿着出边走y步后到达的顶点相同。
在满足条件1的情况下max(x,y)最小。
在满足条件1和2的情况下min(x,y)最小。
在满足条件1、2和3的情况下x>=y。
如果不存在满足条件1的x、y，输出-1 -1。

输入格式
第一行两个正整数n和q。

第二行n个正整数a[1],a[2],…,a[n]。

下面q行，每行两个正整数a,b，表示一组询问。

输出格式
输出q行，每行两个整数。

数据范围

n,q≤500000,
a[i]≤n,
a,b≤n

输入样例：

12 5
4 3 5 5 1 1 12 12 9 9 7 1
7 2
8 11
1 2
9 10
10 5

输出样例：

2 3
1 2
2 2
0 1
-1 -1

题解

这道题和那道基环树森林是类似的, 从在子树上 和 在环上 考虑

先用dfs, 跑同一个基环树上的所有点, 并找出环

我们使用倍增的方法, 处理环上的每棵子树

对于两个节点, 且二者不在同一颗基环树上, 明显 -1, -1

然后就是倍增找父节点,

直接通过 较大深度的节点 向上走 走到x 的, x y同一颗子树, 答案明显 二者深度分别减去 lca深度

然后是 两者在同意深度, 向上同时走

1.最后按通常情况 f[x][0], 应该是lca, 但是我们由于x, y可能在不同的子树上,

所以当 f[x][0] != 0, 是 lca = f[x][0], 答案和上一样, x y同一颗子树

2.f[x][0] == 0, 明显 x, y都走到了自己所在子树的根节点, 也就是环上

那么按照题意, 选择是让 x -> y, 还是 y -> x, 计算答案即可

实现直接套板子, lca倍增板子, 和基环树dfs序找环(少改改)

struct STFrom {
    int f[N][20], dep[N], lg[N], t;//N为节点的数量
    int *h, *ne, *to, *fa;
    bool *v;
    void init(int n, int* H, int* Ne, int* T, int* F, bool* V) {
        t = log2(n - 1) + 1; h = H, ne = Ne, to = T, fa = F, v = V; lg[0] = -1;
        rep(i, 1, n) dep[i] = 0, lg[i] = lg[i >> 1] + 1;
    }
    void bfs(int s) {
        queue<int> q; q.push(s); dep[s] = 1; fa[s] = s;
        rep(i, 0, t) f[s][i] = 0;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int i = h[x], y = to[i]; i; y = to[i = ne[i]]) if (!v[y] && !dep[y]) {
                fa[y] = s; dep[y] = dep[x] + 1; f[y][0] = x; q.push(y);
                for (int j = 1; j <= t; ++j) f[y][j] = f[f[y][j - 1]][j - 1];
            }
        }
    }
    int lca(int x, int y) {
        if (dep[x] > dep[y]) swap(x, y);
        for (int k = dep[y] - dep[x]; ~lg[k]; k ^= 1 << lg[k]) y = f[y][lg[k]];
        if (x == y) return x;
        per(i, lg[dep[y]], 0) if (f[x][i] ^ f[y][i]) x = f[x][i], y = f[y][i];
        return f[x][0];
    }
} ST;

int n, m, _, k, cas;
int h[N], ne[N << 1], to[N << 1], tot;
int id[N], fa[N], st[N], top, d[N], cir[N];
bool v[N], vis[N];

void add(int u, int v) { ne[++tot] = h[u]; to[h[u] = tot] = v; }

int dfs(int x, int e) {
    int s = 0;
    for (int i = h[x], y = to[i]; i; y = to[i = ne[i]]) if (i ^ e)
        if (!vis[y]) vis[y] = 1, id[y] = id[x], s = s ^ dfs(y, i ^ 1);
        else st[++top] = y, s = i & 1 ? y : -y;
    if (s) st[++top] = x, v[x] = 1;
    if (abs(s) == x) {
        if (s == x) rep (i, 2, top) d[st[i]] = d[st[i - 1]] + 1, ST.bfs(st[i]);
        else if (s == -x) per (i, top - 1, 1) d[st[i]] = d[st[i + 1]] + 1, ST.bfs(st[i]);
        return cir[id[x]] = d[x], d[x] = 0;
    }
    return s;
}

int main() {
    IOS; cin >> n >> m; tot = 1;
    rep (i, 2, n) { int a; cin >> a; add(i, a); add(a, i); }
    ST.init(n, h, ne, to, fa, v);
    rep (i, 1, n) if (!vis[i]) vis[i] = 1, id[i] = i, top = 0, dfs(i, 0);
    rep (i, 1, m) {
        int x, y; cin >> x >> y;
        if (id[x] ^ id[y]) cout << "-1 -1\n";
        else if (fa[x] == fa[y]) {
            int lc = ST.dep[ST.lca(x, y)];
            cout << ST.dep[x] - lc << ' ' << ST.dep[y] - lc << '\n';
        } else {
            int a = ST.dep[x] - 1, b = ST.dep[y] - 1; x = fa[x], y = fa[y];
            int c = (d[y] - d[x] + cir[id[x]]) % cir[id[x]], d = cir[id[x]] - c;
            if (max(a + c, b) < max(a, b + d)) cout << a + c << ' ' << b << '\n';
            else if (max(a + c, b) > max(a, b + d) || min(a + c, b) > min(a, b + d))
                cout << a << ' ' << b + d << '\n';
            else cout << a + c << ' ' << b << '\n';
        }
    }
    return 0;
}