트리/이진 트리
코드트리 메신저
4gats
2024. 3. 7. 16:52
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
처음에는 가장 간단하게 DFS 구현을 해보았다.
최대 깊이가 20이어서 시간 초과 났다.
그 다음에는 노드에 cnt를 주고
init() 할 때 Bottom-up으로
권한에 따라서 cnt를 증가시키고 문제를
풀려고 해보았다.
부모 교환 -> LCA처럼 같아질 때까지 부모도 같게 만든다.
권한 변환 -> 변환하고 Bottom-up
이 두개는 문제가 없으나..
이거는 알림망 설정이 불가능하다.
알림망 설정에 필요한 것
밑에서 위로 올라올 때
"얼마"의 권한이 남은 애들이
"몇 개" 인가?
결국 답은 "이차원 배열로 만들기"이다.
int node_info[100004][22];
<구현>
1 ≤ 주어지는 이진트리의 최대 깊이() ≤ 20
이 조건은 매우 중요한 조건이다.
세기(authority) 값도 제한이 20으로 되기 때문이다.
부모 바꾸기
1. 알람이 꺼져있다면, 즉 이어져있다면
알람을 켜서 흔적을 지운다.
2. swap 한다
3. 과거의 부모의 알람이 꺼져있었다면
알람을 꺼서 bottom up으로 추가해준다.
<소스 코드>
|
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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
#include <iostream>
#include <vector>
using namespace std;
int n, q;
int arr[100004];
int parent[100004];
// 해당 노드가 받는 메시지 수
int val[100004];
bool alarm[100004];
// 각 노드의 authority 최대 20개
int node_info[100004][22];
void init()
{
for (int i = 1; i <= n; i++)
cin >> parent[i];
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
// 이진트리의 최대 깊이는 20
// 권한의 최대값은 20
if (arr[i] > 20)
arr[i] = 20;
}
for (int i = 1; i <= n; i++) {
int cur = i;
int author = arr[i];
node_info[cur][author]++;
// 부모까지 올라간다
while (parent[cur] != 0)
{
if (author <= 0)
break;
cur = parent[cur];
author--;
if (author)
node_info[cur][author]++;
val[cur]++;
}
}
}
void toggle(int idx)
{
// 붙인다
if (alarm[idx])
{
int cur = parent[idx];
int dist = 1;
while (cur != 0)
{
// 세기는 최대 20개
for (int i = dist; i <= 21; i++)
{
val[cur] += node_info[idx][i];
// 하위 트리에서 올라온 세기를 늘려줘야함
if (i > dist)
node_info[cur][i - dist] += node_info[idx][i];
}
// 끊겨있으면 종료
if (alarm[cur])
break;
cur = parent[cur];
dist++;
}
alarm[idx] = false;
}
// 자른다
else
{
int cur = parent[idx];
int dist = 1;
while (cur != 0)
{
// 세기는 최대 20개
for (int i = dist; i <= 21; i++)
{
val[cur] -= node_info[idx][i];
// 하위 트리에서 올라온 세기를 줄여줘야함
if (i > dist)
node_info[cur][i - dist] -= node_info[idx][i];
}
if (alarm[cur])
break;
cur = parent[cur];
dist++;
}
alarm[idx] = true;
}
}
// 권한 변경
void change_author(int idx, int author)
{
int past = arr[idx];
// 권한의 크기는 20까지만 유의미하다
author = min(author, 20);
arr[idx] = author;
// 과거 값 없애고
node_info[idx][past]--;
if (!alarm[idx]) {
int cur = parent[idx];
// 거리를 증가시켜나간다
int dist = 1;
while (cur != 0) {
// past - dist = 0 일 때까지
if (past >= dist)
val[cur]--;
if (past > dist)
node_info[cur][past - dist]--;
// 알람이 켜져있는 곳까지
if (alarm[cur])
break;
cur = parent[cur];
dist++;
}
}
// 현재 값으로 바꿔준다
node_info[idx][author]++;
if (!alarm[idx]) {
int cur = parent[idx];
int dist = 1;
while (cur != 0) {
if (author >= dist)
val[cur]++;
if (author > dist)
node_info[cur][author - dist]++;
if (alarm[cur])
break;
cur = parent[cur];
dist++;
}
}
}
void change_parent(int v1, int v2)
{
// past alarm 저장
bool p_a1 = alarm[v1];
bool p_a2 = alarm[v2];
// 알람이 꺼져있다면 일단 알람을 켜서 흔적을 지운다.
if (!alarm[v1])
toggle(v1);
if (!alarm[v2])
toggle(v2);
swap(parent[v1], parent[v2]);
// 과거 부모의 알람이 꺼져있었다면 알람을 다시 꺼준다
if (!p_a1)
toggle(v1);
if (!p_a2)
toggle(v2);
}
void print_count(int idx) {
cout << val[idx] << "\n";
}
|
cs |