HDU 2586. How far away ？

发表于 分类于

链接

http://acm.hdu.edu.cn/showproblem.php?pid=2586

题意

多次询问，求树形图上两点间距离

思路一

重链剖分

将一个点与其拥有子树节点数目的节点相连，形成一条重链，一颗树最多有 $logn$ 条重链
当 $x$ 和 $y$ 不在一条重链上时，将所在链顶点深度大的那个点往上跳，直到在一条链上

时间复杂度：$O((n+m)logn)$

代码

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
#include<bits/stdc++.h>
using namespace std;
const int N=4e4+5;
int n,m;
int cnt,to[N*2],val[N*2],nxt[N*2],head[N];
int fa[N],depth[N],top[N],son[N],size[N];
int dist[N];
void init() {
    cnt=0;
    memset(head,0,sizeof head);
    memset(son,0,sizeof son);
}
void addedge(int u,int v,int w) {
    cnt++;
    to[cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void dfs1(int u,int d) {
    depth[u]=d;
    size[u]=1;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        if(v==fa[u]) continue;
        fa[v]=u;
        dist[v]=dist[u]+val[i];
        dfs1(v,d+1);
        size[u]+=size[v];
        if(size[v]>size[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int t) {
    top[u]=t;
    if(!son[u]) return;
    dfs2(son[u],t);
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        if(v==son[u]||v==fa[u]) continue;
        dfs2(v,v);
    }
}
int lca(int a,int b) {
    while(top[a]!=top[b]) {
        if(depth[top[a]]>depth[top[b]])  a=fa[top[a]];
        else b=fa[top[b]];
    }
    return depth[a]<depth[b]?a:b;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--) {
        cin>>n>>m;
        init();
        for(int i=1;i<n;i++) {
            int u,v,w;
            cin>>u>>v>>w;
            addedge(u,v,w);
            addedge(v,u,w);
        }
        dfs1(1,0);
        dfs2(1,1);
        for(int i=1;i<=m;i++) {
            int a,b;
            cin>>a>>b;
            cout<<dist[a]+dist[b]-2*dist[lca(a,b)]<<endl;
        }
    }
     return 0;
}

思路二

树上倍增法

设 $f[x][k]$ 表示 $x$ 的 $2^k$ 辈祖先：$f[x][k]=f[f[x][k-1]][k-1]$

基于 $f$ 数组计算 $LCA(a,b)$ :

  • 设 $d[b] \ge d[a]$

  • 用二进制思想，把 $b$ 向上调整到与 $a$ 同一深度

  • 若 $a=b$，$LCA=a$

  • 用二进制思想，把 $a,b$ 向上调整，保持二者在同一深度且不相会

  • 此时 $a,b$ 差一步就相会了，它们的父节点 $f[a][0]$ 就是 $LCA(a,b)$

时间复杂度为 $O((n+m)\log n)$

代码

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
#include<bits/stdc++.h>
using namespace std;
const int N=4e4+5;
int n,m;
int cnt,to[N*2],val[N*2],nxt[N*2],head[N];
int dist[N],d[N],f[N][20];
int t;
void init() {
    t=(int)log(n)/log(2)+1;
    cnt=0;
    memset(head,0,sizeof head);
}
void addedge(int u,int v,int w) {
    cnt++;
    to[cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void bfs() {
    queue<int>q;
    q.push(1);
    d[1]=1;
    while(q.size()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i],w=val[i];
            if(d[v]) continue;
            q.push(v);
            d[v]=d[u]+1;
            dist[v]=dist[u]+w;
            f[v][0]=u;
            for(int i=1;i<=t;i++) f[v][i]=f[f[v][i-1]][i-1];
        }
    }
}
int lca(int a,int b) {
    if(d[a]>d[b]) swap(a,b);
    for(int i=t;i>=0;i--) if(d[f[b][i]]>=d[a]) b=f[b][i];
    if(a==b) return b;
    for(int i=t;i>=0;i--) if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];
    return f[a][0];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--) {
        cin>>n>>m;
        init();
        for(int i=1;i<n;i++) {
            int u,v,w;
            cin>>u>>v>>w;
            addedge(u,v,w);
            addedge(v,u,w);
        }
        bfs();
        for(int i=1;i<=m;i++) {
            int a,b;
            cin>>a>>b;
            cout<<dist[a]+dist[b]-2*dist[lca(a,b)]<<endl;
        }
    }
    return 0;
}

思路三

Tarjan 算法

使用并查集“向上标记法”优化，这是一个离线算法

在 DFS 过程中：

  • 将已经访问完毕并且回溯的节点标记为 $2$

  • 将已经开始递归单尚未回溯的节点标记为 $1$

  • 未访问过的节点没有标记

对于正在访问的 $x$，它到根节点的路径已经标记为 $1$

若 $y$ 是已经访问回溯的节点，则 $LCA(x,y)$ 就是 $y$ 向上走遇到的第一个标记为 $1$ 的节点

用并查集进行优化，将已经标记为 $2$ 的节点与它的父节点（标记必为 $1$ ）合并

时间复杂度为 $O(n+m)$

代码

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
#include<bits/stdc++.h>
using namespace std;
const int N=4e4+5;
int n,m;
int cnt,to[N*2],val[N*2],nxt[N*2],head[N];
int st[N],dist[N],fa[N];
vector<pair<int,int> >query[N];
int ans[205];
int init() {
    cnt=0;
    memset(head,0,sizeof head);
    memset(st,0,sizeof st);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++) query[i].clear();
}
void addedge(int u,int v,int w) {
    cnt++;
    to[cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void addquery(int a,int b,int id) {
    query[a].push_back(make_pair(b,id));
    query[b].push_back(make_pair(a,id));
}
int get(int x) {
    if(fa[x]==x) return x;
    return fa[x]=get(fa[x]);
}
void tarjan(int u) {
    st[u]=1;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i],w=val[i];
        if(st[v]) continue;
        dist[v]=dist[u]+w;
        tarjan(v);
        fa[v]=u;
    }
    for(int i=0;i<query[u].size();i++) {
        int v=query[u][i].first,id=query[u][i].second;
        if(st[v]==2) {
            int lca=get(v);
            ans[id]=dist[u]+dist[v]-2*dist[lca];
        }
    }
    st[u]=2;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--) {
        cin>>n>>m;
        init();
        for(int i=1;i<n;i++) {
            int u,v,w;
            cin>>u>>v>>w;
            addedge(u,v,w);
            addedge(v,u,w);
        }
        for(int i=1;i<=m;i++) {
            int a,b;
            cin>>a>>b;
            addquery(a,b,i);
            addquery(b,a,i);
        }
        tarjan(1);
        for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
    }
    return 0;
}