(최장 체인) 템플릿 문제
입력 설명 Input Description 입력의 첫 번째 동작은 두 갈래 나무의 결점 수를 위한 정수 N을 포함하고 결점 표시는 1에서 N까지입니다.다음 N행, 이 N행의 i행은 두 개의 정수 l[i], r[i]를 포함하고 결점 i의 왼쪽 아들과 오른쪽 아들의 번호를 나타낸다.만약에 l[i]가 0이면 결점 i에 왼쪽 아들이 없다는 것을 나타내고, 마찬가지로 r[i]가 0이면 오른쪽 아들이 없다는 것을 나타낸다.
출력 설명 Output Description 출력은 두 갈래 나무의 최장 체인 길이를 위한 정수 1개를 포함합니다.
샘플 입력 Sample Input 5 2 3 4 50 6 0 0
샘플 출력 샘플 출력 4
데이터 범위 및 알림 Data Size & Hint [예시 설명] 4-2-1-3-6은 이 두 갈래 나무 중 가장 긴 체인입니다.
【데이터 규모】 10%의 데이터에 대해 N≤10이 있다.40%의 데이터에 대해 N≤100이 있음;50%의 데이터에 대해 N≤1000이 있음;60%의 데이터에 대해 N≤10000; 있음;100%의 데이터에 대해 N≤100000이 있고 나무의 깊이가 32768을 넘지 않도록 보장합니다.
【제시】 두 갈래 나무에 대한 귀속 정의: 두 갈래 나무는 비어 있거나 뿌리 결점, 왼쪽 나무, 오른쪽 나무로 구성되어 있다.왼쪽 나무와 오른쪽 나무는 각각 두 갈래 나무다.뿌리 나무와 두 갈래 나무의 세 가지 주요 차이가 있음을 주의하십시오. 1.나무의 결점 개수는 적어도 1이고 두 갈래 나무의 결점 개수는 0이다.2. 나무에서 결점의 최대 도수는 제한이 없고 두 갈래 나무 결점의 최대 도수는 2이다.3. 나무의 결점은 왼쪽, 오른쪽의 구분이 없고 두 갈래 나무의 결점은 왼쪽, 오른쪽의 구분이 있다.최장 체인에 관하여: 최장 체인은 이 두 갈래 나무 중 가장 긴 간단한 경로, 즉 중복 결점을 거치지 않는 경로이다.두 갈래 나무 중 가장 긴 사슬의 시작, 끝 결점은 모두 잎 결점이라는 것을 쉽게 증명할 수 있다.
우선 제목은 나무 한 그루를 주고 구성할 수 있는 사슬의 최대 길이를 구하라는 뜻이다.우리는 두 개의 연결된 노드의 거리가 1이라는 것을 알 수 있기 때문에 우리는 귀속적인 방법을 운용하여 부모 노드에 연결된 길이의 값을 하위 노드에 부여할 수 있다.즉, 만약에 이런 두 갈래 나무가 있는데 그 중의 한 노드에 두 개의 잎 노드가 연결되어 있다면 우리는 이 두 개의 잎 노드의 값부치가 1이라고 말한다. 이 부 노드와 이 잎 노드가 형성하는 사슬의 길이가 1이라는 것을 나타낸다. 따라서 이 부 노드가 형성하는 사슬의 길이를 가장 크게 하려면 왼쪽 아들 노드의 값과 오른쪽 아들 노드의 값을 더해야 한다. 즉, 이 부 노드가 형성하는 사슬의 최대치이다.이 부노드의 값은 가장 큰 아들 노드의 값+1을 취하여 이 부노드의 부노드와 그 부노드가 구성하는 체인의 최대값을 표시하기 때문에 이 부노드의 값은 2이어야 한다.마지막으로 모든 노드가 구성할 수 있는 최장 체인의 길이를 다시 한 번 검색하고 현재 찾은 최장 체인의 길이를 끊임없이 비교하여 최대치를 찾아 값을 부여한다.
#include
#include
int n;
int son[100001][2]={0};
int deep[100001]={0};
int ans;
void find(int a);
int max(int a,int b);
void found(int a);
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&son[i][0],&son[i][1]);
if (son[1][0])
find(son[1][0]);
if (son[1][1])
find(son[1][1]);
for (int i=1;i<=n;i++)
found(i);
printf("%d",ans);
}
void find(int a)
{
if (son[a][0])
find(son[a][0]);
if (son[a][1])
find(son[a][1]);
deep[a]=max(deep[son[a][0]],deep[son[a][1]])+1;
int b=deep[son[a][0]]+deep[son[a][1]];
if (b>ans)
ans=b;
}
void found(int a)
{
int b=deep[son[a][0]]+deep[son[a][1]];
if (b>ans)
ans=b;
}
int max(int a,int b)
{
if (a>b)
return a;
else
return b;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.