MYF

POJ 1986 Distance Queries

Posted on | In | | Visitors

题目链接

POJ 1986

方法：LCA

题目分析

题目大意

树上共有n个点，m条边，给出m条边，然后有k个查询，问两个点之间的最短距离。

解析

树上两个点之间的最短距离即两个点到根节点的最短距离减去两者最近公共祖先到根节点的距离。

代码

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
130
131
132
133
134
135
136
137
138
139
140
141
#pragma comment(linker, "/STACK:10240000000,10240000000")///扩栈，要用c++交，用g++交并没有什么卵用。。。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 100005
#define PI acos(-1.0)
using namespace std;
typedef long long LL;
const int N = 40005;

int n , m , pre[N] ,rt[N], mcnt;
int dis[N];
bool vis[N];
struct edge
{
    int x , next, w;
} e[N << 1];

int dep[N] , f[17][N] , Lev , s[N];///1<<16 < N, f[j][i] 表示i的第2^j个祖先

void dfs(int x , int fa, int w)///也可以用bfs，但bfs不能统计节点孩子个数
{
    dis[x]=dis[fa]+w;
    dep[x] = dep[fa] + 1;
    f[0][x] = fa , s[x] = 1;
    for (int i = pre[x] ; ~i ; i = e[i].next)
    {
        int y = e[i].x;
        if (y != fa)
        {
            dfs(y , x,  e[i].w);
            s[x] += s[y];///节点x的孩子个数
        }
    }
}
void bfs(int rt)///不需要求孩子个数，同时防止暴栈
{
    queue<int> q;
    q.push(rt);
    f[0][rt] = 0,dep[rt] = 1,vis[rt] = 1;
    while(!q.empty())
    {
        int fa = q.front();
        q.pop();
        for (int i = pre[fa] ; ~i ; i = e[i].next)
        {
            int x = e[i].x;
            if (!vis[x])
            {
                dep[x] = dep[fa] + 1;
                f[0][x] = fa ,vis[x] = 1;
                q.push(x);
            }
        }
    }
}
int LCA(int x , int y)
{
    if (dep[x] > dep[y]) swap(x , y);
    for (int i = Lev ; i >= 0 ; -- i)///找y的第dep[y] - dep[x]个祖先
        if (dep[y] - dep[x] >> i & 1)
            y = f[i][y];
    if (x == y) return y;
    for (int i = Lev ; i >= 0 ; -- i)
        if (f[i][x] != f[i][y])
            x = f[i][x] , y = f[i][y];
    return f[0][x];
}
int get_kth_anc(int x , int k) ///找x的第k个祖先
{
    for (int i = 0 ; i <= Lev ; ++ i)
        if (k >> i & 1)
            x = f[i][x];
    return x;
}
void init()
{
    memset(pre , -1 , sizeof(pre));
    memset(rt,0,sizeof(rt));
    memset(dis, 0, sizeof(dis));
    mcnt = 0;
}
void addedge(int x,int y, int z)
{
    e[mcnt].x = y,
    e[mcnt].w=z;
    e[mcnt].next = pre[x],
    pre[x] = mcnt ++;
}

int main()
{
    int i , j , x , y , z,anc,m;
    init();
    while (scanf("%d%d",&n,&m)!=EOF) {
        for (i = 1 ; i <= m ; ++ i)
        {
            char ch[2];
            scanf("%d%d%d%s",&x,&y,&z,ch);
            addedge(x,y,z);
            addedge(y,x,z);
            rt[y]  =x;
        }
        for(int i=1; i<=n; i++)
        {
            if(rt[i]==0)
            {
                anc = i;
                break;
            }
        }
        dfs(anc , 0, 0);
        for (j = 1 ; 1 << j < n ; ++ j)
            for (i = 1 ; i <= n ; ++ i)
                f[j][i] = f[j - 1][f[j - 1][i]];
        Lev = j - 1;
        int k;
        scanf("%d",&k);
        for (int i=0; i<k; i++) {
            scanf("%d%d",&x,&y);
            if (dep[x] < dep[y])
                swap(x , y);
            printf("%d\n",dis[x]+dis[y]-2*dis[LCA(x , y)]);
        }
    }
    
    return 0;
}