나뭇잎에 데이터가 주어진 경우 나뭇잎이

Question

인 경우 방향성이없는 나무 T이 있고 그곳에는 T.leaves - 모든 나뭇잎 (각 v는 d(v) = 1)이 있어야합니다. 우리는 알고있다 : |T.leaves| 및 distance between u and v for each u,v in T.leaves.
다른 말로하면 : 우리는 방향이없는 나무가 있으며 잎의 수와 2 개의 잎 사이의 거리를 알고 있습니다.
how many inside vertices (d(v)>1) are in the tree을 찾아야합니다.

참고 : 잎이 2 개 밖에 없지만 잎의 간격이 2^30이면 너무 오래 걸릴 수 있으므로 전체 나무를 만드는 것은 불가능합니다.

가장 짧은 거리부터 시작하여 계산 방법을 시도했습니다. 많은 버텍스가 그들 사이에 있고, 가장 가까운 버텍스를 추가합니다. 그러나 이것에 대해서는 몇 가지 수식 f (leaves_counted, next_leaf)가 필요합니다. 그러나 나는 그것을 찾을 수 없었습니다.
어떤 아이디어가 있습니까?

Answer 1

의견에서 계속됩니다. 이것은 특정 (압축 된) 에지를 확인하여 거리의 반복없이 새로운 꼭지점 인 n을 중간에 부착 할 수 있는지 확인하는 방법입니다.

좋아, 그래서 당신은 세 개의 숫자를 찾을 필요가 : l (문제의 모서리의 왼쪽 노드에서 연결 지점의 거리)의 연결 지점에서 새로운 노드의 x (거리) 및 l 대칭 r (.)

물론, 세트 L의 모든 노드 y (트리의 왼쪽 부분)에 대해, A과의 거리가 (동일한 번호로 n에의 거리 달라야를 호출 할 수 있습니다 dl whi ch는 같아야합니다. l + x). 그렇지 않은 경우이 특정 가장자리에 대한 해결책이 없습니다. R에있는 노드의 경우도 마찬가지이며, 각각 dr 및 r + x입니다.

l + x = dl

r + x = dr

r+l = dist(A,B)

세 방정식, 세 개의 숫자 : 위가 보유하고있는 경우

는 다음 세 가지 방정식이있다. 이것이 해결책이있는 경우에 당신은 맞은 가장자리를 찾아 냈다.

최악의 경우 모든 가장자리에 대해 위의 과정을 반복해야하지만 최적화가 가능하다고 생각합니다. L 및 R의 거리 확인은 추가 검색에서 트리 부분 중 하나를 제외 할 수 있습니다. 트리를 구성하지 않고도 노드의 수를 어떻게 든 얻는 것이 가능할 수도 있습니다.

Answer 2

이진 트리에 L 잎이있는 경우 트리 모양에 관계없이 L-1 내부 정점이 있습니다.

쉽게 증명할 수 있습니다. 하나의 노드 (루트) 노드로 트리부터 시작하십시오. 그런 다음 리프를 가져 와서 두 개의 자손을 추가하여 리프를 내부 정점으로 변환하고 리프에 추가합니다. 이것은 한 리프 (이전 노드)를 제거하고 하나의 내부 노드와 두 리프를 추가합니다. 즉, net은 +1 내부 노드와 +1 리프입니다.첫 번째 리프와 0 개의 내부 노드로 시작하기 때문에 항상 | 잎 | = | 내부 노드 | +1 --- 어떤 트리 형태도이 프로세스에 의해 생성 될 수 있습니다. 4 개 단풍 나무의 모든 두 가지 형태의

다음

예 (사소한 좌우 대칭을 위해 저장) : 내부 꼭지점의 수는 항상 당신이 실제로이를 구축 할 수 있습니다 3.