개인적으로 백준에서 보는 것보다 pdf로 보는 게 더 편한 것 같다.
한 자릿수 서브태스크 배점들을 보고 왜 이렇게 짜게 주나 했는데,
하나씩 풀다 보니까 기가 막힌 점수 배분인 것 같다.
부분 문제 1 ~ 4 풀이는 노드의 번호를 1-base 기준으로 작성했고, 부분 문제 5 풀이는 0-base 기준으로 작성했습니다.
궁금하신 점은 댓글로 남겨주시면 답변해 드리겠습니다!
문제 요약
"모든 $[i,j]$꼴의 정점 집합에 대해 만들어진 각 virtual tree의 가중치의 합을 구하라." 정도이다.
부분 문제 1 (5점)
$N\le 300$이다. $O(N^3)$이 넉넉하게 돌아갈 수준이다.
모든 $[i,j]$를 직접 돌면서 dfs를 돌리면 된다.
웬만해서는 코드를 짜보려고 했는데, 점수 대비 구현량의 가성비가 너무 떨어져서 생략한다...
부분 문제 2 (6점)
$N\le 4\ 000$이다. $O(N^2)$이 넉넉하게 돌아갈 수준이다.
각 $i$에 대해서 모든 $[i,j]$를 잘 구할 방법이 있을 것이다.
$i$를 루트로 하는 트리를 생각하자. 간선 $(u,v)$에 대해 일반성을 잃지 않고 $u$가 $v$의 부모라고 하자.
간선 $(u,v)$는 $T_v$의 $i$보다 큰 가장 작은 노드가 $j$로 이용되는 시점부터 $n$이 $j$로 이용되는 시점까지 더해진다.
이는 dfs 한 번에 전부 처리할 수 있다.
따라서 전체 시간 복잡도 $O(N^2)$에 잘 된다.
코드
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define siz(x) int((x).size())
#define mup(x,y) x = min(x,y)
using ll = long long;
using vi = vector<int>;
#define fi first
#define se second
const int N = 4003, M = 1e9+7;
int n, root;
vector<ii> adj[N];
pair<int,ll> dfs(int s, int e = 0) {
int mv = n+1; ll res = 0;
if (s > root) mup(mv,s);
for (auto [u,w] : adj[s]) if (u != e) {
auto [_mv,_res] = dfs(u,s);
mup(mv,_mv);
res = (res+w*ll(n-_mv+1))%M;
res = (res+_res)%M;
}
return {mv,res};
}
int maintenance_costs_sum(vi U, vi V, vi W) {
n = siz(U)+1;
rep(i,0,n-2) {
adj[U[i]+1].push_back({V[i]+1,W[i]});
adj[V[i]+1].push_back({U[i]+1,W[i]});
}
ll ans = 0;
rep(i,1,n) {
root = i;
ans = (ans+dfs(root).se)%M;
}
return ans;
}
부분 문제 3 (10점)
기지에 매겨진 번호는 $0$번 기지를 루트로 한 트리의 전위 순회 순서 (Preorder) 중 하나이다.
이 조건은 한 마디로 dfs ordering의 성질들을 자유롭게 이용 가능하다는 것이다.
간선 $(u,v)$에 대해 일반성을 잃지 않고 $u$가 $v$의 부모라고 하자.
$T_v$ 속 정점들은 오직 $[v,v+|T_v|)$로만 이루어져 있다.
따라서 $(u,v)$가 더해지지 않는 $(i,j)$들은 다음 세 가지로 나눌 수 있다.
- $[1,v)$에서 뽑는 경우
- $[v,v+|T_v|)$에서 뽑는 경우
- $[v+|T_v|,N]$에서 뽑는 경우
각각 개수는 $\binom k 2$ 꼴로 해서 $\binom N 2$에서 빼주면 간선을 몇 번 더할지 구할 수 있다.
이렇게 여사건에 대해서 생각하는 아이디어가 이 부분 문제에서 얻어갈 부분이다.
코드
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define siz(x) int((x).size())
using ll = long long;
using vi = vector<int>;
const int N = 2.5e5+3, M = 1e9+7;
int n;
vector<ii> adj[N];
ll ans;
int dfs(int s = 1, int e = 0) {
int sub = 1;
for (auto [u,w] : adj[s]) if (u != e) {
int _sub = dfs(u,s);
ll cnt = ll(n)*(n-1)/2;
cnt -= ll(_sub)*(_sub-1)/2;
cnt -= ll(u-1)*(u-2)/2;
cnt -= ll(n - (u+_sub-1))*(n - (u+_sub-1)-1)/2;
cnt %= M;
ans = (ans + w * cnt)%M;
sub += _sub;
}
return sub;
}
int maintenance_costs_sum(vi U, vi V, vi W) {
n = siz(U)+1;
rep(i,0,n-2) {
adj[U[i]+1].push_back({V[i]+1,W[i]});
adj[V[i]+1].push_back({U[i]+1,W[i]});
}
dfs();
return ans;
}
부분 문제 4 (26점)
각 기지에 연결된 통로가 최대 $2$개이다.
이 조건은 직선형 그래프이다.
부분 문제 3에서는 dfs ordering의 성질에 의해 제외할 부분이 연속 구간을 이루고 있어서 해결할 수 있었다.
하지만 직선형 그래프나 일반적인 트리는 그렇지 않다.
그러면 전부 제외할 연속 구간들의 집합으로 다룰 수 없을까?
간선 $(u,v)$가 연결하는 두 컴포넌트에 속한 각 연속 구간들의 길이 $\ell$에 대해 $\binom \ell 2$의 합을 여사건으로 취하면 된다.
우선, 직선형 배열의 앞쪽에서부터 $i$개 선택했을 때의 값들과, 뒤쪽에서부터 $i$개를 선택했을 때의 값들을 각각 $O(N\times \alpha (N))$에 전처리해두자. disjoint set 자료구조를 이용하면 된다.
그러면 각 간선에 대해 $O(1)$만에 간선을 몇 번 더할지 결정할 수 있다.
코드
산술 오버플로우를 주의하며 구현하자.
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define siz(x) int((x).size())
using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
const int N = 2.5e5+3, M = 1e9+7;
int n;
vector<ii> adj[N];
ll pfx[N], sfx[N];
int a[N], b[N];
bool exists[N];
template <const int N>
struct disjoint_set {
int sz[N], par[N];
void clear() { iota(par,par+N,0), fill(sz,sz+N,1); }
int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
bool same(int a, int b) { return find(a) == find(b); }
void merge(int a, int b) {
a = find(a), b = find(b);
if (sz[a] > sz[b]) swap(a,b);
sz[b] += sz[a], par[a] = b;
}
int size(int x) { return sz[find(x)]; }
};
disjoint_set<N> ds;
int solve() {
ll res = 0;
auto upd = [&](int a, int b) {
ll x = ds.size(a), y = ds.size(b);
res -= x*(x-1)/2 + y*(y-1)/2;
ds.merge(a,b), x = ds.size(b);
res += x*(x-1)/2, res %= M;
};
ds.clear();
rep(i,1,n) {
exists[a[i]] = true;
if (a[i] > 1 and exists[a[i]-1]) upd(a[i]-1,a[i]);
if (a[i] < n and exists[a[i]+1]) upd(a[i]+1,a[i]);
pfx[i] = res;
}
res = 0, ds.clear(), fill(exists,exists+N,0);
per(i,1,n) {
exists[a[i]] = true;
if (a[i] > 1 and exists[a[i]-1]) upd(a[i]-1,a[i]);
if (a[i] < n and exists[a[i]+1]) upd(a[i]+1,a[i]);
sfx[i] = res;
}
ll ans = 0;
rep(i,1,n-1) {
ans += (ll(n)*(n-1)/2-pfx[i]-sfx[i+1])%M*b[i];
ans %= M;
}
return ans < 0 ? ans+M : ans;
}
void build() {
int t = 0;
function<void(int,int)> dfs = [&](int s, int e) {
a[++t] = s;
for (auto [u,w] : adj[s]) if (u != e) b[t] = w, dfs(u,s);
};
rep(i,1,n) if (siz(adj[i]) == 1) { dfs(i,0); break; }
}
int maintenance_costs_sum(vi U, vi V, vi W) {
n = siz(U)+1;
rep(i,0,n-2) {
adj[U[i]+1].push_back({V[i]+1,W[i]});
adj[V[i]+1].push_back({U[i]+1,W[i]});
}
build();
return solve();
}
부분 문제 5 (53점)
$N\le 2.5\times 10^5$이다. 로그가 두 개까지 붙을 수 있겠다.
부분 문제 4의 직선형 그래프에서의 방식을 그대로 적용할 수 없는 이유는 무엇인가?
각 간선을 기준으로 양쪽 컴포넌트에 담긴 연속 구간들에 대한 정보를 파악하기 어렵기 때문이다.
컴포넌트의 연속 구간들의 집합을 생각해 보자.
정확히 그 여집합도 연속 구간들의 집합 형태를 띨 것이다.
컴포넌트 연속 구간들과 컴포넌트 여집합 연속 구간들은 번갈아 나타난다.
따라서 두 집합의 크기 차이는 기껏해야 $1$이다.
그렇다면, 컴포넌트 연속 구간들과 컴포넌트 여집합 연속 구간들을 함께 관리할 수 있을까?
즉, 부분 문제 4의 경우에서 접두사를 가지고 간선으로 구분되는 반대쪽 접미사를 따로 전처리하지 않고 함께 관리할 수 있냐는 것이다.
그 방법을 잘 고민해 보자.
두 컴포넌트의 연속 구간 집합을 잘 합칠 수 있을까?
합칠 때 이용할 수 있는 좋은 아이디어로는 smaller to larger 테크닉이 있다.
이를 이용해서 연속 구간들의 변경 사항을 잘 관리해 주면, 컴포넌트 연속 구간들과 컴포넌트 여집합 연속 구간들을 전부 관리할 수 있다.
아래 그림을 참고하자.
기존에 $[L_1,R_1]$과 $[L_2,R_2]$를 갖는 컴포넌트가 있다. 컴포넌트의 여집합에는 $[e\ell_1,e\ell_2]$가 있다.
여기에 $[\ell,r]$이라는 새 연속 구간을 합치려면 $R_1$과 $\ell$의 인접 여부, $r$과 $L_2$의 인접 여부를 따져 다음 두 가지를 처리하면 된다.
- 잘 따져서 $[L_1,R_1]$과 $[L_2,R_2]$를 빼주고, $[\ell,r]$을 넣어준다.
- 잘 따져서 $[e\ell_1,er_2]$를 빼주고, $[e\ell_1,er_2]$와 $[e\ell_2,er_2]$를 넣어준다.
이를 이용해 각 간선에 대해서 서브트리의 컴포넌트 연속 구간들과 컴포넌트 여집합 연속 구간들의 개수의 합을 $\binom N 2$에서 빼준 다음에 가중치를 곱해서 전체 답에 더해주는 방식으로 풀 수 있다.
코드
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define siz(x) int((x).size())
using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
const int N = 2.5e5+3, M = 1e9+7;
int n, par[N];
vector<ii> adj[N];
ll ans, inc[N], exc[N];
set<ii> segs[N];
int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
inline ll C(ll x) {
if (x < 2) return 0;
return x*(x-1)/2%M;
}
inline ll C(ll x, ll y) { return C(y-x+1); }
void merge(int x, int y) {
x = find(x), y = find(y);
if (siz(segs[x]) > siz(segs[y])) swap(x,y);
par[x] = y;
for (auto [l,r] : segs[x]) {
auto it = segs[y].lower_bound({l,r});
auto [L1,R1] = (it == begin(segs[y]) ? ii(-1,-1) : *prev(it));
auto [L2,R2] = (it == end(segs[y]) ? ii(n,n) : *it);
int el1 = R1+1, er1 = l-1, el2 = r+1, er2 = L2-1, nl = l, nr = r;
if (it != begin(segs[y]) and R1+1 == l) {
inc[y] -= C(L1,R1), inc[y] %= M;
segs[y].erase({L1,R1});
nl = L1;
}
if (it != end(segs[y]) and L2-1 == r) {
inc[y] -= C(L2,R2), inc[y] %= M;
segs[y].erase({L2,R2});
nr = R2;
}
exc[y] += C(el1,er1)+C(el2,er2)-C(el1,er2), exc[y] %= M;
inc[y] += C(nl,nr), inc[y] %= M;
segs[y].insert({nl,nr});
}
}
void dfs(int s = 0, int e = -1) {
segs[s].insert({s,s}), exc[s] = C(s)+C(n-s-1);
for (auto [u,w] : adj[s]) if (u != e) {
dfs(u,s);
ans -= (inc[find(u)]+exc[find(u)])*w, ans %= M;
merge(s,u);
}
}
int maintenance_costs_sum(vi U, vi V, vi W) {
n = siz(U)+1;
rep(i,0,n-2) {
adj[U[i]].push_back({V[i],W[i]});
adj[V[i]].push_back({U[i],W[i]});
ans += C(n)*W[i], ans %= M;
}
iota(par,par+N,0), dfs();
return ans < 0 ? ans+M : ans;
}'PS 문제들' 카테고리의 다른 글
| [KAIST Run 2023] Merging Branches (BOJ 28056) ★ (0) | 2023.07.02 |
|---|---|
| [KTSC 2023 #1] 던전 (BOJ 27508) (0) | 2023.03.15 |
| [POI 03/04 Stage 1] Strings(트리 모델 만들기) (BOJ 1839) (0) | 2023.02.10 |
| [USACO Gold 2014 March] Sabotage (BOJ 10019) (0) | 2023.02.10 |
| [Coder's High 2014] Tons Of Damage (0) | 2023.02.09 |
