MYF

HDU 2586 How far away ？

Posted on | In | | Visitors

题目链接

HDU 2586

题目类型：LCA模版题

题目分析

题目大意

n个点，m个询问，然后给出n-1条边，m个询问。问询问的两个点之间的距离。

解析

树上两个点的最短距离为两个点到根节点的距离减去两倍的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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#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 ++;
}
void work()
{
    int i , j , x , y , z,anc,m;
    init();
    scanf("%d%d",&n,&m);
    for (i = 1 ; i < n ; ++ i)
    {
        scanf("%d%d%d",&x,&y,&z);
        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;
    for (int i=0; i<m; 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)]);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        work();
    }
    return 0;
}