codeforces #612 div2 D - Numbers on Tree (그래프, 수학, 구현)

https://codeforces.com/contest/1287/problem/D

실패할 조건을 찾은데서 그친 문제. 시험볼 당시엔 좀만 보면 풀 수 있을 것 같다고 생각했지만, 꽤 오래 생각해봐도 못풀었다.

 

<문제설명>

최대크기 2000의 트리가 주어진다. 각 정점마다 a[i]값을 갖는다. (이 값은 주어지지 않는다. 찾아내야 함)

 

이 때, 각 정점이 루트가되는 서브트리에서 현재 정점의 a값보다 작은 a값을 갖는 정점들의 수를 c값이 주어질때 가능한 a배열을 구해라.

 

 

예시

위->아래, 왼쪽->오른쪽 순서대로 각 정점 번호가 1,2,3,4,5이다. (오른쪽 리프노드가 5번정점이다.)  크게 쓰인 수가 a값이고 괄호 안의 값이 c값이다.

 

<풀이>

1. 실패조건

각 정점을 루트로 하는 서브트리의 크기를 sz[i]라고 하자. 그러면 c[i]<=sz[i]-1 이어야 한다. sz배열은 전체 루트노드부터 한 번의 dfs로 알 수 있다.

 

2. vector<int> order[i] : c[i]값을 바탕으로 valid한 순서를 담아준다. 마지막엔 order[root]를 바탕으로 a배열을 만들 것.

예를들어 위의 그림에서, order[3] = {4,3} 이다. 

또한, order[root] = {4,1,3,5,2} 이므로 각 숫자의 인덱스인 a[i] = {2,5,3,1,4}가 된다.

 

2-1. order 벡터를 어떻게 만들까?

 

dfs하면서 order[n1], order[n2], order[n3]를 만들어 놨다면, 이 셋들은 그냥 갖다 붙여놔도 valid하다. (순서바꿔서 붙여놔도 된다. 서로 영향을 주지 않기 때문)

 

curr에 인접한 정점들에 order을 초기화해서 concat해둔 벡터에 c[i]번째 자리에 curr을 넣어주기만 하면 된다.

order[curr].insert(order[curr].begin() + c[curr], curr);

 

(이 때 c[curr]값이 sz[curr]-1보다 작거나 같음을 꼭 보장해줘야 한다. 안그러면 runtime error)

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using namespace std;
const int MAX = 2e3 + 3;

int n, a[MAX],c[MAX], sz[MAX];
vector<int> adj[MAX], order[MAX];

bool vst[MAX];
void dfs(int curr) {
	vst[curr] = true;
	sz[curr] = 1;

	for (int next : adj[curr]) {
		if (!vst[next]) {
			dfs(next); //빠져나오면 curr의 next방향 서브트리의 sz모두 초기화
			sz[curr] += sz[next];
			order[curr].insert(order[curr].end(), order[next].begin(), order[next].end());
		}
	}
	if (sz[curr] - 1 < c[curr]) {
		cout << "NO\n";
		exit(0);
	}
	order[curr].insert(order[curr].begin() + c[curr], curr);
}

int main() {
	FAST;
	cin >> n;
	int root;
	for (int i = 1, pp,cc; i <= n; i++) {
		cin >> pp >> cc;
		if (pp == 0) root = i;
		if (pp != 0) adj[pp].push_back(i);
		c[i] = cc;
	}

	memset(vst, 0, sizeof(vst));
	dfs(root);
	
	cout << "YES\n";
	for (int i = 0; i < n; i++)
		a[order[root][i]] = i+1;
	for (int i = 1; i <= n; i++)
		cout << a[i] << " ";
	cout << '\n';
		
}