Menu
Article ACM

CodeForces 832D Misha, Grisha and Underground

NodeKey

NodeKey

• 3 min read

昨晚疯狂掉分的第四题，其实比第三题还简单……
搞不懂cf又不按套路出牌了……先是来一个巨简单的，让每个人都不得不去签到，随后是坑题，然后是压轴题，再然后才是普通题，难题……

题意：
给你一棵树，每次询问3个点，要你求出3个点两两构成的路径中选出两条，使得他们相交的长度最长。

思路：
这道题并不难，先求出LCA，再分类讨论一下即可，但是但是但是但是！！分类的情况会非常非常多，就图而言就有4种，还要考虑各自的位置。
必须得总结一下，不然跟着写会疯掉。
考虑让每个点为两条路径的相交点，分三种情况讨论。
而每种情况中，当两个路径各自的lca相同时，除了该点的所在的路径以外只要求出另外两个点的lca长度 – 三点lca 路径长度即可。
否则，就只剩下第三个点为另外两点的父亲这一情况,所以长度为 根节点到所讨论的结点距离 减去 非父亲结点的另外两个结点的 lca 的距离。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary));

const int maxn = 1e5 + 5;

int n, q, v, idx = 1, qidx = 1;
int head[maxn], qhead[maxn];
bool vis[maxn];
int root[maxn];
int lca[maxn * 3], dis[maxn];

struct node {
    int to, next;
    node() {}
    node(int _to, int _next) { to = _to, next = _next; }
} edges[maxn * 2];

struct qnode {
    int to, next, idx;
    qnode() {}
    qnode(int _to, int _next, int _idx) { to = _to, next = _next, idx = _idx; }
} qedges[maxn * 6];

int a[maxn], b[maxn], c[maxn];

void addEdge(int u, int v)
{
    edges[idx] = node(v, head[u]);
    head[u] = idx++;
    edges[idx] = node(u, head[v]);
    head[v] = idx++;
}

void addQEdge(int u, int v, int id)
{
    qedges[qidx] = qnode(v, qhead[u], id);
    qhead[u] = qidx++;
    qedges[qidx] = qnode(u, qhead[v], id);
    qhead[v] = qidx++;
}

int findRoot(int x)
{
    return root[x] == x ? x : root[x] = findRoot(root[x]);
}

void tarjan(int u)
{
    root[u] = u;
    vis[u] = true;
    for (int it = qhead[u]; it != 0; it = qedges[it].next) {
        int v = qedges[it].to;
        if (vis[v])
            lca[qedges[it].idx] = findRoot(v);
    }
    for (int it = head[u]; it != 0; it = edges[it].next) {
        int v = edges[it].to;
        if (!vis[v]) {
            dis[v] = dis[u] + 1;
            tarjan(v);
            root[v] = u;
        }
    }
}

int query(int da, int ab, int ac, int bc)
{
    if (ab == ac)
        return da - dis[ab] + dis[bc] - dis[ab] + 1;
    else
        return da - max(dis[ab], dis[ac]) + 1;
}

int main()
{
    scanf("%d %d", &n, &q);
    range(i, 2, n)
    {
        scanf("%d", &v);
        addEdge(i, v);
    }
    each(i, q)
    {
        scanf("%d %d %d", a + i, b + i, c + i);
        addQEdge(a[i], b[i], i * 3);
        addQEdge(a[i], c[i], i * 3 + 1);
        addQEdge(b[i], c[i], i * 3 + 2);
    }
    tarjan(1);
    q *= 3;
    for (int i = 0; i < q; i += 3) {
        int al = query(dis[a[i / 3]], lca[i], lca[i + 1], lca[i + 2]);
        int bl = query(dis[b[i / 3]], lca[i + 2], lca[i], lca[i + 1]);
        int cl = query(dis[c[i / 3]], lca[i + 1], lca[i + 2], lca[i]);
        printf("%d\n", max(al, max(bl, cl)));
    }
    return 0;
}
Share