「AHOI2008」紧急集合-LCA

给出一颗 $n$ 个节点的无权树， $m$ 次询问，每次给出三个点编号为 $a$ ，$b$ ， $c$ ，询问到这三个点距离最小的点的编号以及其距离和。

链接

题解

首先，如果每次询问都只有两个点，这个问题就很简单，只要是树上的路径上的点就可以，寻找树上的路径其实就是寻找 $LCA$ 的过程。这可以启发我们对于三个点的情况的思考。

如果这里有三个点，我们来认真的思考一下。经过上一问的启发，我们来思考一下能不能运用 $LCA$ 来解决这道题。

我们可以发现，树上三个点的三对 $LCA$ 一定有两个是相同的。这是一件想想的话比较显然的事情。必然能够找到某个节点，让三个点中的两个在一侧，一个在另一侧。而这个点就是两个公共的 $LCA$ 。思考的再深入些（并且结合瞎蒙），我们会发现这个相同的 $LCA$ 肯定是深度最小的一个 $LCA$ 。

这里，我们首先可以显而易见的发现，这个点必须在三个点互相通达的路径上。

我们再思考一下 $LCA$ 与路径和的关系。假设我们知道 $a$ 和 $b$ 的 $LCA$ 是 $x$ ，而且 $x$ 是上述的3个 $LCA$ 中深度最大的那个，那么可以发现从 $x$ 到 $a$ 的距离加上从 $x$ 到 $b$ 的距离一定是最小的。根据上面的结论，我们知道 $a$ ， $c$ 和 $b$ ， $c$ 的 $LCA$ 点 $y$ 一定在一个点上，而且这个 $y$ 一定比 $x$ 深度小。

那么这个时候，我们会发现此时 $a$ ， $b$ ， $c$ 到 $x$ 的距离和是最小的。证明的话可以这么想：如果 $x’$ 比 $x$ 高，那么虽然 $c$ 到 $x$ 的距离减小了 $w$ ，但是 $a$ ， $b$ 到 $x’$ 的距离均增大了 $w$ ，显然距离和增大。如果 $x’$ 比 $x$ 低，有一个节点到 $x’$ 的距离减小了 $w$ ，剩下两个节点到 $x’$ 的距离均增大了 $w$ ，显然距离和也增大。

所以我们就找到了到三个点距离和最小的点：这三个点的三对 $LCA$ 中，深度大的那两个LCA就是答案。

我们在求 $LCA$ 之前，可以先预处理出深度$dep$，那么从节点 $u$ 到 $v$ 的路径长度就是$dis = dep[u] + dep[v] - 2*dep[lca(u,v)]$。运用这个式子分别算出 $a$ , $b$ , $c$ 到 $a1$ , $b1$ , $c1$（三个 $LCA$ ）的距离，最后发现总的 $dis$ 居然是轮换式：$ans = dep[a]+dep[b]+dep[c]-dep[a1]-dep[b1]-dep[c1]$，所以就不用分类讨论了。

$LCA$ 我用了树链剖分来求，顺带处理深度。

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstdio>
#include <cctype>
#include <vector>
using namespace std;

namespace fast_io {
    inline char read() {
        static const int IN_LEN = 1000000;
        static char buf[IN_LEN], *s, *t;
        return s==t?(((t=(s=buf)+fread(buf,1,IN_LEN,stdin))== s)?-1:*s++) : *s++;
    }
    inline void read(int &x) {
        static bool iosig;
        static char c;
        for (iosig = false, c = read(); !isdigit(c); c = read()) {
            if (c == '-') iosig = true;
            if (c == -1) return;
        }
        for (x = 0; isdigit(c); c = read())
            x = ((x+(x<<2))<<1) + (c ^ '0');
        if (iosig) x = -x;
    }
    const int OUT_LEN = 1000000;char obuf[OUT_LEN], *ooh = obuf;
    inline void print(char c) {
        if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
        *ooh++ = c;
    }
    inline void print(int x) {
        static int buf[30], cnt;
        if (x == 0) 
            print('0');
        else {
            if (x < 0) print('-'), x = -x;
            for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
            while (cnt) print((char)buf[cnt--]);
        }
    }
    inline void flush() {
        fwrite(obuf, 1, ooh - obuf, stdout);
    }
}using namespace fast_io;

const int MAXN = 510000;

vector<int> edge[MAXN];

int n,m;
int dep[MAXN],siz[MAXN],fa[MAXN],son[MAXN],top[MAXN],id[MAXN],cnt = 1;


//添加从a到b的无向边
void addedge(int a,int b){
    edge[a].push_back(b);
    edge[b].push_back(a);
}

//树链剖分的第一个dfs
void dfs1(int nown,int f,int depth){
    siz[nown] = 1,fa[nown] = f,dep[nown] = depth;
    int maxsum = -1;son[nown] = 0;
    for(int i = 0;i<edge[nown].size();i++){
        int to = edge[nown][i];
        if(to == f) continue;
        dfs1(to,nown,depth+1);
        if(siz[to] > maxsum) maxsum = siz[to],son[nown] = to;
        siz[nown] += siz[to];
    }
}

//树链剖分的第二个dfs
void dfs2(int nown,int topf){
    id[nown] = cnt++;top[nown] = topf;
    if(son[nown] == 0) return;
    dfs2(son[nown],topf);
    for(int i = 0;i<edge[nown].size();i++){
        int to = edge[nown][i];
        if(to == fa[nown]|| to == son[nown]) continue;
        dfs2(to,to);
    }
}

//求a,b两点的LCA
int lca(int a,int b){
    while(top[a]!=top[b]){
        if(dep[top[a]] < dep[top[b]]) swap(a,b);
        a = fa[top[a]];
    }
    if(dep[a] < dep[b]) swap(a,b);
    return b;
}

//初始化以及dfs
void init(){
    read(n),read(m);
    int a,b;
    for(int i = 1;i<=n-1;i++){
        read(a),read(b);
        addedge(a,b);
    }
    dfs1(1,0,1);
    dfs2(1,1);
}

//回应询问
void solve(){
    int a,b,c,a1,b1,c1,ans,dis;
    for(int i = 1;i<=m;i++){
        read(a),read(b),read(c);
        //a1,b1,c1的意义见下
        a1 = lca(a,b),b1 = lca(b,c),c1 = lca(c,a);
        dis = 0;
        if(a1 == b1) 
            ans = c1;
        else if(b1 == c1)
            ans = a1;
        else if(c1 == a1)
            ans = b1;
        //计算dis的公式
        dis = dep[a] + dep[b] + dep[c] - dep[a1] - dep[b1] - dep[c1];
        print(ans),print(' '),print(dis),print('\n');
    }
}

int main(){
    init();
    solve();
    flush();
    return 0;
}

「AHOI2008」紧急集合-LCA

链接

题解

代码

See Also

Comments