POI14 Supercomputer

문제

www.acmicpc.net/problem/10128

10128번: Supercomputer

루트가 정해진 트리가 하나 주어지고, 트리의 각 노드는 프로세스로, 어떤 노드의 프로세스를 실행하기 위해서는 그 노드의 조상 노드를 모두 실행해야 한다.

이때, 한번에 K개의 프로세스를 동시에 실행할 수 있으며, 전체 실행 단계를 최소화해야한다.

트리는 하나로 고정되어 주어지고, K값이 쿼리로 들어온다.

$N<=10^6, Q<=10^6$

 

풀이

노드 $u$에 대해, 루트에서 그 노드까지의 거리를 $d(u)$, 그 노드에서 자식으로 갈 수 있는 최대 길이를 $h(u)$라 정의하자.

 

Observation 1 : 트리의 높이를 $h(1)$, 노드의 개수를 $N$개라고 했을 때 답은 $\lceil \frac{N}{K} \rceil$ 이상이고, $h(1)$이상이다.

한번에 선택할 수 있는 노드의 수가 최대 K개이기 때문에 답은 $\lceil \frac{N}{K} \rceil$이상이고, 또한 1번 정점으로부터 가장 깊이가 깊은 노드까지의 길이 $h(1)$의 경로를 생각하면 한 단계당 경로의 노드를 최대 한개씩만 선택할 수 있기 떄문에 $h(1)$이상이다.

이 관찰을 통해서 답을 결정하는 요소에는 노드의 개수도 있지만, 트리의 깊이 또한 중요하다는 것을 알 수 있다.

 

Observation 2 : 각 단계에서 선택할 수 있는 노드들 중, $h(u)$가 가장 큰 노드들부터 선택하는 것이 최적의 전략이다.

기본적으로 지금 $h(u)$를 선택했다면 현재 단계를 포함해서 앞으로 적어도 $h(u)$개의 추가 단계가 필요하다는 것을 의미하니, 가장 추후에 드는 단계가 많이 필요한 노드부터 선택해야 할 필요가 있다. 엄밀한 증명은 다음의 관찰을 한 후에 증명한다.

 

한번의 단계에 최대한 많이 선택을 해야 하는데, 최대 K씩만 선택할 수 있기 때문에 거꾸로 K개 선택할 수 없는 단계에 주목하자. K보다 적게 선택했다는 것은 현재 선택할 수 있는 노드가 K개 미만이라는 것이고, K개 선택했다는 것은 현재 선택할 수 있는 노드의 수가 K개 이상임을 의미한다.

 

$r_k(t)$를 K개씩 선택하는 알고리즘에서 t번째 단계에서 선택하는 노드의 수로 정의하자.

 

Observation 3 : Observation 2의 알고리즘에 따라 선택한다면 $r_k(t)<K$라면 $d(u)<=t$인 모든 노드들이 t단계 전까지 모두 선택되어 있다.

귀납법을 이용하여 증명한다.

$r_k(1)=1<K$ 일 때는 $d(u)<=1$인 u는 루트 하나밖에 없으니, 성립한다.

 

$r_k(t)<K$라 하자. 만약 $r_k(t-1)=K$라면, 귀납적으로 $d(u)<=t-1$인 모든 노드들은 선택되었고, 이로 인해 $d(u)=t$인 노드들은 모두 잠금 해제 되었다. 또한, t-1단계까지는 깊이가 t-1인 노드만 선택할 수 있기 때문에, 이 외의 다른 노드들은 선택할 수 없다. 따라서 현재 선택할 수 있는 노드들은 오직 깊이가 t인 노드 전부이며, $r_k(t)<K$이니, 선택할 수 있는 모든 노드를 선택하여 깊이 $t$인 모든 노드를 선택한다. 따라서 귀납 조건을 만족한다.

 

이제 $r_k(t-1)=K$이고, 더 나아가 $r_k(t-1)=K$인 노드가 연속하여 $B$개 있다고 하자.

귀납 가정을 만족하지 않는다고 가정하자. 즉, $r_k(t)<K$이지만 깊이 t의 노드들 중 선택되지 않은 정점 u가 존재한다고 가정하자. u의 B개 조상을 건너뛴 노드 v는 $r_k(t-B-1)<K$이기 때문에 귀납 가정에 의해 선택되었을 것이다. 따라서 v 다음의 노드는 B개가 있지만, u는 시간 t까지도 선태되지 않았기 때문에 B-1개 이하의 노드들이 그 사이에 선택되었을 것이다. 그렇다면, u의 조상 집합에 있는 노드들 중 아무것도 선택하지 않게 되는 단계 p가 존재하고, $r_k(p)=K$이다. 그 단계에서 u의 조상 집합이 아닌 다른 노드를 선택했다는 것은, 최소한 깊이가 t이상인 서로 다른 노드가 K개 존재한다는 것이고, 그러한 노드들을 해당 단계에서 선택했다는 것이다. 하지만 이가 의미하는 것은 p이후의 모든 단계에서 각 노드들의 자식들을 하나씩 선택했다고 가정해도 t번째 단계까지 왔을 때 선택할 수 있는 노드가 K개는 존재한다는 것이다. 하지만 단계 t에서는 노드를 K개 미만으로밖에 선택하지 못했으니, 모순이다. 즉 귀납 조건은 성립한다.

 

Observation 3를 이용하여 Observation 2의 알고리즘이 최적의 전략임을 증명하자.

먼저 Observation 2의 알고리즘으로 선택을 진행한 후, $r_k(t)<K$인 최대의 t를 p라 하자. 전체 노드들을 깊이 p이하와, 초과로 나누어 각 단계에서 Observation 2의 알고리즘의 선택보다 최적의 선택이 없음을 보이자.

p개의 단계로는 최대 깊이 p이하의 노드들만 선택할 수 있기 때문에 깊이 p이하의 노드들을 정확히 p단계를 이용하여 모두 선택했다면, 이보다 더 적게 선택할 수 있는 방법은 없다. 깊이가 p초과인 노드들에 대해서는 모두 $r_k(t)=K$이니, 한번에 선택할 수 있는 모든 노드들을 다 선택한 것이니, 이보다 더 적게 선택할 수는 없다.

 

이제, 최적의 전략을 찾았으니 위 전략을 그대로 priority queue를 이용하여 시뮬레이션해주면 각 쿼리당 $O(NlogN)$의 시간복잡도에 해결할 수 있어, 전체 $O(QNlogN)$에 해결할 수 있다.

 

마지막 Observation 2의 증명 과정을 다시 생각해보면 답의 형태가 매우 간단한 꼴로 요약됨을 알 수 있다.

t이상($t'>=t$)의 $r_k(t')$ 들의 합을 $sum_t$라 정의하자.

$r_k(t)<K$인 최대의 t를 찾아 이를 p라 한다면 답은 $p+\lceil \frac{sum_{p+1}}{K} \rceil$이다.

하지만 시뮬레이션을 해보기 전까지 해당 p를 정확히 알지 못한다는 문제가 있다.

 

Observation 4 : p보다 작거나, p보다 큰 모든 t에 대해 $t+\lceil \frac{sum_{t+1}}{K} \rceil$값은 모두 p에 대한 값보다 작다.

먼저, $p+\lceil \frac{sum_{p+1}}{K} \rceil$ 대신, $p+\frac{sum_{p+1}}{K}$을 구하고, 이 값에 ceil을 씌우자.

만약 t가 p보다 작을 경우, $p-t$와 $\frac{sum_{t+1}}{K}-\frac{sum_{p+1}}{K}$를 비교하면, $\frac{r_k(t+1)+r_k(t+2)+ ... +r_k(p)}{K}$이고, $r_k(t')<=K$이니, $\frac{r_k(t+1)+r_k(t+2)+ ... +r_k(p)}{K}<=\frac{(p-t)K}{K}=p-t$이니, p에대한 값이 t에대한 값보다 작거나 같다.

만약 t가 p보다 클 경우, p 이후의 $r_k(t)=K$이니, p에 대한 값이 t에 대한 값과 같다.

 

즉, 굳이 p를 몰라도 단순히 $t+\lceil \frac{sum_{t+1}}{K} \rceil$값을 최대화하면 된다.

sum 함수의 정의 또한 같은 논리로 실제 시뮬레이션 과정에서의 t이상($t'>=t$)의 $r_k(t')$ 들의 합 대신, 높이 t+1 이상의 노드들의 수로 정의할 수 있다.

 

이제 쿼리로 들어오는 K에 대해 $\frac{Kt+sum_{t+1}}{K}$을 최대화 하면 되기 때문에, 분자에 있는 값은 K에 대한 일차함수임을 이용해 CHT를 이용하여 해결한다.

 

시간 복잡도 : $O(N+QlogN)$

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

int N, Q;
int A[MAXN+10];

int dep[MAXN+10];
vector<int> adj[MAXN+10];
int B[MAXN+10];

void dfs(int now, int d)
{
	dep[now]=d;
	for(int nxt : adj[now])
	{
		dfs(nxt, d+1);
	}
}

struct Line
{
	ll a, b;
};

double cross(Line p, Line q) { return (double)(p.b-q.b)/(q.a-p.a); }

struct CHT
{
	vector<Line> S;
	void push(Line p)
	{
		while(S.size()>1 && cross(S[S.size()-2], S[S.size()-1])>cross(S[S.size()-1], p)) S.pop_back();
		S.push_back(p);
	}
	ll query(ll x)
	{
		int lo=0, hi=S.size();
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(cross(S[mid], S[mid-1])<=x) lo=mid;
			else hi=mid;
		}
		return S[lo].a*x+S[lo].b;
	}
}cht;

int main()
{
	scanf("%d%d", &N, &Q);
	for(int i=1; i<=Q; i++) scanf("%d", &A[i]);
	for(int i=2; i<=N; i++)
	{
		int u, v=i;
		scanf("%d", &u);
		adj[u].push_back(i);
	}
	dfs(1, 1);

	for(int i=1; i<=N; i++) B[dep[i]]++;
	for(int i=N; i>=1; i--) B[i]+=B[i+1];

	for(int i=1; i<=N; i++)
	{
		if(B[i]==0) break;
		cht.push({i, B[i+1]});
		//printf("%d %d\n", i, B[i+1]);
	}
	for(int i=1; i<=Q; i++)
	{
		int K=A[i];
		ll t=cht.query(K)+K-1;
		t/=K;
		printf("%lld\n", t);
	}
}