반응형

문제 출처 :


https://www.acmicpc.net/problem/8012



알고리즘 분석 :


문제 해결에 필요한 사항

1. LCA(Lowest Common Ancestor) :: http://www.crocus.co.kr/660


이 문제는 [1761번] 정점들의 거리 :: http://www.crocus.co.kr/663 문제와 매우 유사하나 간선이 모두 1이라는 점만 다르다.


그리고 입력받는 방식이 조금 다른 것 외에는 코드 자체가 똑같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
scanf("%d", &tmp);
 
if (chk == true)
{
    chk = false;
    a = tmp;
    tmpa = a;
    scanf("%d", &b);
    tmpb = b;
    m--;
}
 
else
{
    a = tmpb;
    tmpa = a;
 
    b = tmp;
    tmpb = b;
}



이 부분에서 만약 입력이

1

3

2

5

로 들어온다면


1 3

3 2

2 5로 a와 b를 설정해주는 방식을 담아두었다.


그 외에는 http://www.crocus.co.kr/663에서 같은 코드에 대한 알고리즘을 설명해 두었으니, 그 부분을 참고하도록 하자.


소스 코드 : 


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
145
146
147
148
149
150
151
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
 
#define swap(a,b){int t = a; a = b; b = t;}
#define MAX_NODE 40001
 
using namespace std;
 
// depth :: 노드의 깊이(레벨)
// ac[x][y] :: x의 2^y번째 조상을 의미
int depth[MAX_NODE];
int ac[MAX_NODE][20];
 
typedef pair<int, int> pii;
vector<pii> graph[MAX_NODE];
 
// 1에서 x까지의 거리
int dist[MAX_NODE];
 
int max_level;
 
// DP(ac)배열 만드는 과정
void getTree(int here, int parent, int val)
{
    // here의 깊이는 부모노드깊이 + 1
    depth[here] = depth[parent] + 1;
 
    if (here != 1)
        dist[here] += dist[parent] + val;
 
    // here의 1번째 조상은 부모노드
    ac[here][0] = parent;
 
    // MAX_NODE에 log2를 씌어 내림을 해준다.
    max_level = (int)floor(log2(MAX_NODE));
 
    for (int i = 1; i <= max_level; i++)
    {
        // tmp :: here의 2^(i-1)번째 조상
        int tmp = ac[here][i - 1];
        ac[here][i] = ac[tmp][i - 1];
    }
 
    // dfs 알고리즘
    int len = graph[here].size();
    for (int i = 0; i < len; i++)
    {
        int there = graph[here][i].first;
        if (there != parent)
            getTree(there, here, graph[here][i].second);
    }
}
 
int main()
{
    int n, m;
 
    scanf("%d", &n);
 
    // 양방향 그래프 형성
    for (int i = 1; i < n; i++)
    {
        int from, to;
        scanf("%d %d", &from, &to);
        graph[from].push_back(pii(to, 1));
        graph[to].push_back(pii(from, 1));
    }
 
    // make_tree에 1,0이 들어가기때문에 0은 -1로 지정
    depth[0] = -1;
 
    // 루트 노드인 1번 노드부터 트리 형성
    getTree(1, 0, 0);
 
    // 쿼리문 시작
    scanf("%d", &m);
 
    if (m == 1)
    {
        printf("0");
        return 0;
    }
    int tmpa, tmpb;
    bool chk = true;
 
    int a, b, tmp;
    int ans = 0;
    while (m--)
    {
        scanf("%d", &tmp);
 
        if (chk == true)
        {
            chk = false;
            a = tmp;
            tmpa = a;
            scanf("%d", &b);
            tmpb = b;
            m--;
        }
 
        else
        {
            a = tmpb;
            tmpa = a;
 
            b = tmp;
            tmpb = b;
        }
 
        if (depth[a] != depth[b])
        {
            // depth[b] >= depth[a]가 되도록 swap
            if (depth[a] > depth[b])
                swap(a, b);
 
            // b를 올려서 depth를 맞춰준다.
            int j = 0;
            for (int i = max_level; i >= 0; i--)
            {
                // b의 2^i번째 조상이 a의 depth보다 크거나 같으면 계속 조상을 타고간다.
                if (depth[a] <= depth[ac[b][i]])
                    b = ac[b][i];
            }
        }
 
        int lca = a;
 
        if (a != b)
        {
            for (int i = max_level; i >= 0; i--)
            {
                if (ac[a][i] != ac[b][i])
                {
                    a = ac[a][i];
                    b = ac[b][i];
                }
                lca = ac[a][i];
            }
        }
 
        ans += dist[tmpa] + dist[tmpb] - 2 * dist[lca];
    }
    printf("%d\n", ans);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[3653번] 영화 수집  (0) 2017.03.16
[7894번] 큰 숫자  (0) 2017.03.15
[1761번] 정점들의 거리  (0) 2017.03.15
[11437번] LCA  (0) 2017.03.15
[11438번] LCA 2  (0) 2017.03.15

티스토리툴바