다음과 같은 트리가 있다고 가정해보자. 1번 정점이 루트이고, DFS 방문 순서대로 번호가 붙여져있다.
이 트리를 배열에 저장하면 각 정점을 루트로 하는 서브트리를 구간으로 나타낼 수 있게 된다. (번호가 DFS 방문 순서대로 되어있어야 성립한다. 일반적인 트리가 주어지는 경우 구간을 계산하기 위한 번호를 다시 붙여야 한다.)
구간의 시작지점은 각 정점이 처음 방문 되었을 때, 끝 지점은 그 정점에서의 DFS함수가 끝났을 때의 번호를 저장함으로써 알 수 있다.
이것을 이용하는 것이 오일러 경로 테크닉이다.
오일러 경로 테크닉을 활용하는 대표적인 문제로 회사 문화 2,3,4가 있다.
영선회사에는 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다. 모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다.
이때 i번째 직원이 직속 상사로부터 w만큼 칭찬받거나 i번쨰 직원이 칭찬받은 정도를 출력하는 쿼리가 여러개 주어지면 각 쿼리에 대해 계산하거나 출력하는 문제이다.
세그먼트 트리를 활용하여 i번째 직원이 w만큼 칭찬받으면 i번째 직원의 서브트리 구간에 값을 더해준다. 그리고 조회할 때는 i번쨰 직원의 서브트리의 루트, 즉 구간의 첫번째 지점을 조회하면 된다.
#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 100001
using namespace std;
long long tree[MAX*4];
long long lazy[MAX*4];
pair<int, int> range[MAX];
// (세그먼트 트리)
int cnt=0;
vector<int> V[MAX];
void dfs(int x) {
range[x].first=++cnt;
for (int i=0;i<V[x].size();i++) {
dfs(V[x][i]);
}
range[x].second=cnt;
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++) {
int a;
cin>>a;
V[a].push_back(i);
}
cnt=0;
dfs(1);
while (m--) {
int t;
cin>>t;
if (t==1) {
int a,b;
cin>>a>>b;
update_tree(1, n, 1, range[a].first, range[a].second, b);
} else if (t==2) {
int a;
cin>>a;
cout<<sum_tree(1, n, 1, range[a].first, range[a].first)<<"\n";
}
}
}회사 문화 3은 회사 문화 2에서 반댓방향으로 칭찬이 진행되는 문제이다. 상사가 아래에 있는 부하를 칭찬하는게 아니라, 부하가 상사를 칭찬하면 그 위로 쭉 사장까지 모두 칭찬을 받는다.
세그먼트 트리를 활용하여 i번째 직원이 w만큼 칭찬받으면 구간의 첫번째 지점에 값을 더하고, 그리고 조회할 때는 i번째 직원의 서브트리 구간의 합을 구하면 된다.
// ...
while (m--) {
int t;
cin>>t;
if (t==1) {
int a,b;
cin>>a>>b;
update_tree(1, n, 1, range[a].first, range[a].first, b);
} else if (t==2) {
int a;
cin>>a;
cout<<sum_tree(1, n, 1, range[a].first, range[a].second)<<"\n";
}
}부하 방향의 내리칭찬과 상사 방향의 내리칭찬이 섞이며 주어지는 문제이다. 각 방향의 내리칭찬이 서로 연관이 없으므로, 트리를 2개 사용하여 각각 계산하고 더해주도록 구현하면 된다.
// ...
while (m--) {
int t;
cin>>t;
if (t==1) {
int a,b;
cin>>a>>b;
if (flag) update_tree(f_tree, f_lazy, 1, n, 1, range[a].first, range[a].second, b);
else update_tree(r_tree, r_lazy, 1, n, 1, range[a].first, range[a].first, b);
} else if (t==2) {
int a;
cin>>a;
cout<<sum_tree(f_tree, f_lazy, 1, n, 1, range[a].first, range[a].first) +
sum_tree(r_tree, r_lazy, 1, n, 1, range[a].first, range[a].second)<<"\n";
} else if (t==3) {
flag=!flag;
}
}