树论

倍增法求LCA

【LCA】LuoguP4281 紧急集合

对一棵树，边\((x_i,y_i)\)表示\(x_i,y_i\)之间存在双向边，边权为1，对于\(Q\)个询问，每个询问包含一个三元组\((x,y,z)\)，表示三个人分别所处的树结点编号，求这三个位置的人移动到某个相同点经过的边权和的最小值，给出此最佳集结点与边权和最小值。

此处证明：最短边权和为此情况：集结点为某两个起始点的LCA。

考虑\((x,y)\)的情况，最佳集结点为\(P:x\to y\)路径上任何一个点，\(z\)需要以最短路径走到\(P\)上，若\(lca(x,z)\in P或lca(y,z)\in P\)，则\(lca(x,z)或lca(y,z)\)为最佳集结点，若\(lca(x,z),lca(y,z)\notin P\)，则\(lca(x,y)\)为最佳集结点。

参考解答 
 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
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct edge{int v,next;}a[N];
int depth[N],h[N],tot,fa[N][21],n,m;
struct node{int posi,ans;};
void add(int x,int y)
{
    a[++tot]=(edge){y,h[x]};
    h[x]=tot;
}
void maketree(int x,int father,int d)
{
    fa[x][0]=father,depth[x]=d;
    for(int i=h[x];i;i=a[i].next)
    {
        int v=a[i].v;
        if(v==father) continue;
        maketree(a[i].v,x,d+1);
    }
}
node lca(int x,int y)
{
    int ans=0;
    if(depth[x]<depth[y]) swap(x,y);
    for(int i=20;i>=0;i--)
        if(depth[fa[x][i]]>=depth[y])
            ans+=(1<<i),x=fa[x][i];
    if(x==y) return (node){x,ans};
    for(int i=20;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
        {
            ans+=2*(1<<i);
            x=fa[x][i],y=fa[y][i];
        }
    return (node){fa[x][0],ans+2};
}
int main()
{
    cin>>n>>m;
    int u,v;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    maketree(1,0,1);
    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
            fa[j][i]=fa[fa[j][i-1]][i-1];
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        node p1=lca(x,y),p2=lca(y,z),p3=lca(x,z);
        node p4=lca(z,p1.posi),p5=lca(x,p2.posi),p6=lca(y,p3.posi);
        int ANS=min(p4.ans+p1.ans,
        min(p5.ans+p2.ans,p6.ans+p3.ans));
        if(ANS==p4.ans+p1.ans)
        {
            printf("%d %d\n",p1.posi,ANS);
            continue;
        }
        if(ANS==p5.ans+p2.ans)
        {
            printf("%d %d\n",p2.posi,ANS);
            continue;
        }
        if(ANS==p6.ans+p3.ans)
        {
            printf("%d %d\n",p3.posi,ANS);
            continue;
        }
    }
    return 0;
}

【LCA】【树论】LuoguP3398 仓鼠找sugar

【题目大意】对于一棵树\(T\)，边\((x_i,y_i)\)表示\(x_i,y_i\)存在双向边，有\(Q\)个询问，对于每个询问给出\((a,b,c,d)\)，判断路径\(X:a\to b,Y:c\to d\)是否有交点。

先证明：路径存在交点的充要条件是某路径端点的LCA落在另一条路径上。必要性显然，下证充分性：

假设某一交点为\(P\)，

（1）若路径\(a\to b,c\to d\)在过点后同时上升（走向深度更低的点）,则此点也为路径公共点\((fa_P)\)，转为讨论\(fa_P\)；

（2）同时下降则从逆方向看，转为第一种情况；

（3）若无其他情况，明显得证；

（4）若在某点，一条路径上升，一条路径下降，则得证，后者端点的LCA在前者上。

判断方法：对于\(lca(a,b)=p_1,lca(c,d)=p_2\)，当\(p_1\in Y\)时一定有\(depth_{p_1}\ge depth_{p_2}\)，此时\(lca(c,p_1)=p_1\cup lca(d,p_1)=p_1\)成立。\(p_2\in X\)同理，均不满足则无交点。

参考解答 
 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
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int h[N],tot,n,q,fa[N][25],depth[N],w,x,y,z;
struct edge{int v,next;}a[N];
void add(int x,int y)
{
    a[++tot]=(edge){y,h[x]};
    h[x]=tot;
}
void getdepth(int x,int d,int father)
{
    depth[x]=d,fa[x][1]=father;
    for(int i=h[x];i;i=a[i].next)
    {
        int v=a[i].v;
        if(v==father) continue;
        getdepth(a[i].v,d+1,x);
    }
}
int lca(int x,int y)
{
    if(depth[x]<depth[y]) swap(x,y);
    for(int i=20;i>=1;i--)
        if(depth[fa[x][i]]>=depth[y])
            x=fa[x][i];
    if(x==y) return x;
    for(int i=20;i>=1;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][1];
}
void check()
{
    scanf("%d%d%d%d",&w,&x,&y,&z);
    int p1=lca(w,x),p2=lca(y,z);
    if(depth[p1]>=depth[p2])
    {
        if(lca(y,p1)==p1||lca(z,p1)==p1)
        {
            printf("Y\n");
            return;
        }
    }
    else
    {
        if(lca(w,p2)==p2||lca(x,p2)==p2)
        {
            printf("Y\n");
            return;
        }
    }
    printf("N\n");
}
int main()
{
    scanf("%d%d",&n,&q);
    int u,v;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    getdepth(1,0,1);
    for(int i=2;i<=20;i++)
        for(int j=1;j<=n;j++)
            fa[j][i]=fa[fa[j][i-1]][i-1];
    for(int i=1;i<=q;i++)
        check();
    return 0;
}