【LCA】小机房的树

图论

传送门：CodeVS2370

LCA裸题，此处采用基于RMQ的做法

原理图：

P1

代码如下：

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
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define log_2(x) (log(x)/log(2))
#define LL long long
#define INF 1000000000000
LL n,m,p,nn,x,y,z,tot;
LL ST[800300][25],vis[800030],dep[800030],id[200030],head[200030];
bool q[200030],qq[200030];
struct edge{
    LL v,dist,next;
}
e[200030];
void add(LL x,LL y,LL z){
    tot++;
    e[tot].v=y;
    e[tot].dist=z;
    e[tot].next=head[x];
    head[x]=tot;
}
void search(LL x){
    q[x]=1;
    for (int i=head[x];i;i=e[i].next)
        if (q[e[i].v]==0)
            search(e[i].v);
}
void dfs(LL x,LL dept){
    nn++;
    vis[nn]=x;
    dep[nn]=dept;
    if (id[x]==0) id[x]=nn;
    qq[x]=1;
    
    for (int i=head[x];i;i=e[i].next)
        if (qq[e[i].v]==0){
            dfs(e[i].v,dept+e[i].dist);
            nn++;
            vis[nn]=x;
            dep[nn]=dept;
        }
        
    return;
}
void initRMQ(LL m){
    for (int i=1;i<=m;i++)
        ST[i][0]=dep[i];
    for (int j=1;(1<<j)<=m;j++)
        for (int i=1;i+(1<<j)-1<=m;i++)
            ST[i][j]=min(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
}
LL getRMQ(LL x,LL y){
    LL k=log_2(y-x+1);
    return min(ST[x][k],ST[y-(1<<k)+1][k]);
}
    
LL lca(LL u,LL v){
    LL U=id[u],V=id[v];
    if (U>V) swap(U,V);
    
    return getRMQ(U,V);
}
int main(){
    scanf("%lld",&n);
    for (int i=1;i<n;i++){
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    
    dfs(0,0);
    
    initRMQ(nn);
    
    scanf("%lld",&p);
    for (int i=1;i<=p;i++){
        scanf("%lld%lld",&x,&y);
        LL LCA=lca(x,y); //return the depth of LCA
            printf("%lld\n",dep[id[x]]-LCA+dep[id[y]]-LCA);
    }
    
    return 0;
}