제목

모든 표지가 없고 좌우 아들을 구분하는 뿌리가 있는 두 갈래 나무에 대해 나무 T 1 T_1 T1은 다른 트리에서 사용할 수 있습니다. T 2 T_2T2는 성장하고, 단지 몇 번만 진행하면 T2T_를2 T2의 잎 노드를 어떤 두 갈래 나무로 바꾸는 조작을 할 수 있다.두 갈래 나무 집합 T\mathscr {T} T에 대해 g r o w (T)\mathrm {grow} (\mathscr {T}) grow (T) 는 T\mathscr {T} T의 나무로 성장할 수 있는 모든 집합을 표시합니다.정의 g r o w (T)\mathrm {grow} (\mathscr {T}) grow (T) 는 완비되어 있으며, 유한한 두 갈래 나무만 g r o w (T)\mathrm {grow} (\mathscr {T}) grow (T) 에 없습니다.두 갈래 트리에 T\mathscr {T} T를 집합하고 g r o w (T)\mathrm {grow} (\mathscr {T}) grow (T) 가 완비되었는지 묻습니다.∑ n , ∑ m ≤ 2 ∗ 1 0 6\sum n,\sum m\le 2*10^6 ∑n,∑m≤2∗106

분석

나뭇가지를 각 노드의 좌우 트리로 정의하는 sizesizesize의 minmin은 1,1을 초과하지 않는 두 갈래 나무입니다.다시 말하면 하나의 메인 체인과 다른 몇 개의 잎으로 구성된 두 갈래 나무들이다.
gr o w(T)\mathrm{grow}(\mathscr{T})grow(T)가 완비되어 있고 유한한 나뭇가지만 자라지 못하는 것을 발견할 수 있습니다.한 그루의 나무는 반드시 그 깊이와 같은 나뭇가지로 자랄 수 있기 때문에, 만약 어떤 깊이의 나뭇가지가 모두 자랄 수 있다면, 이 깊이보다 작지 않은 모든 나무도 자랄 수 있기 때문이다.
문제는 모든 나뭇가지가 자랄 수 있는지의 여부로 바뀌었다.입력한 나뭇가지가 아닌 나무는 나뭇가지가 아닌 것이 틀림없기 때문에 무시할 수 있다.
단독 뿌리 노드를 제외하고 모든 나뭇가지를 네 종류로 나눌 수 있다. (1) 뿌리에는 왼쪽 아들이 있지만 오른쪽 아들은 없다.(2) 뿌리는 오른쪽 아들이 있지만 왼쪽 아들은 없다.(3) 뿌리에는 좌우 아들이 있고 왼쪽 자목의 크기는 111이다.(4) 뿌리에는 좌우 아들이 있고 오른쪽 자목의 크기는 111이다.주의하면 두 가지는 중복된 트리를 포함할 수 있습니다.
모든 나뭇가지는 무한종이 있기 때문에 gr o w(T)\mathrm{grow}(\mathscr{T})grow(T)는 완비된 것이고 네 가지 나뭇가지만 완비된 것이다.gr o w(T)\mathrm{grow}(\mathscr{T})grow(T)의 완비 여부를 판단하는 귀속 알고리즘을 고려한다. 1. 만약에 T\mathscr{T}T에 단독 점이 존재한다면 gr o w(T)\mathrm{grow}(\mathscr{T})grow(T)는 반드시 완비된 것이다.2. T\mathscr {T} T에서 첫 번째 종류로 분류될 수 있는 모든 나뭇가지에 대해 왼쪽 트리로 구성된 집합을 T ′\mathscr {T'} T ′로 설정하고 g r o w (T′)\mathrm {grow} (\mathscr {T'}) grow (T′) 가 완비되었는지 판단합니다.후 세 종류의 나뭇가지도 같은 처리를 한다.3. g r o w (T)\mathrm {grow} (\mathscr {T}) grow (T) 는 완비되어 있으며, 이전 단계에서 매번 귀속되는 집합만 완비되어 있다.
시간 복잡도 O(∑n) O(\sum n) O(∑n).

코드

#include
using namespace std;

typedef pair<int, int> pi;

const int N = 2000005;

int m;

struct Tree
{
	int n, *lef, *rig, *size;
	
	void init()
	{
		scanf("%d", &n);
		lef = new int[n + 1]; rig = new int[n + 1]; size = new int[n + 1];
		size[0] = 0;
		for (int i = 1; i <= n; i++) scanf("%d%d", &lef[i], &rig[i]);
	}
	
	bool check(int x)
	{
		if (lef[x] && !check(lef[x])) return 0;
		if (rig[x] && !check(rig[x])) return 0;
		size[x] = size[lef[x]] + size[rig[x]] + 1;
		if (!lef[x] || !rig[x]) return 1;
		return min(size[lef[x]], size[rig[x]]) <= 1;
	}
	
	void clear()
	{
		delete[] lef;
		delete[] rig;
		delete[] size;
	}
}t[N];

bool solve(vector<pi> & vec)
{
	if (!vec.size()) return 0;
	for (pi w : vec) if (t[w.first].size[w.second] == 1) return 1;
	vector<pi> v1, v2, v3, v4;
	for (pi w : vec)
	{
		int x = w.first, y = w.second;
		if (!t[x].lef[y]) v1.push_back(make_pair(x, t[x].rig[y]));
		if (!t[x].rig[y]) v2.push_back(make_pair(x, t[x].lef[y]));
		if (t[x].size[t[x].lef[y]] == 1 && t[x].rig[y]) v3.push_back(make_pair(x, t[x].rig[y]));
		if (t[x].size[t[x].rig[y]] == 1 && t[x].lef[y]) v4.push_back(make_pair(x, t[x].lef[y]));
	}
	vec.clear();
	if (!solve(v1) || !solve(v2) || !solve(v3) || !solve(v4)) return 0;
	return 1;
}

int main()
{
	int T; scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &m);
		for (int i = 1; i <= m; i++)
		{
			t[i].init();
			if (!t[i].check(1)) t[i].clear(), i--, m--;
		}
		vector<pi> vec;
		for (int i = 1; i <= m; i++) vec.push_back(make_pair(i, 1));
		puts(solve(vec) ? "Almost Complete" : "No");
		for (int i = 1; i <= m; i++) t[i].clear();
	}
	return 0;
}