글 읽기 - 반례를..모르겠습니다ㅠㅠ

ssoo2024 3년 전 0

트리를 순회하면서 가중치를 갱신하는 방식으로(아래 코드 주석) 하였는데

바로 틀렸습니다가 뜨더라고요... 혹시 반례좀 알려주시면 정말 감사하겠습니다ㅠㅠ

n이 1인 경우라던지 일자형태 트리 등 여러 테스트 케이스 돌려봤는데 아직 반례를 찾지 못하겠습니다

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

int ans;

typedef struct Node {
	int costToParent = 0; // 부모로 향하는 가중치
	Node* left = NULL;
	Node* right = NULL;
} Node;

int cal(Node* node) {
	if (node == NULL) return 0; // leaf node인 경우 0리턴

	int leftmax = cal(node->left);  // 왼쪽 경로에서 최대값
	int rightmax = cal(node->right); // 오른쪽 경로에서 최대값
	
	ans = max(ans, (leftmax + rightmax)); // 현재 노드 기준으로 (왼쪽 + 오른쪽)이랑 전체 최대값 비교해서 갱신

	return max(leftmax, rightmax) + node->costToParent; // 현재 경로에서 최대값 + 부모로 가는 가중치의 합 리턴
}

int main() {
	ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
	int n, a, b, c; cin >> n;
	vector<Node> tree(n + 1);

	for (int i = 1; i < n; i++) {
		cin >> a >> b >> c; // 부모노드번호, 자식번호, 가중치
        // 왼쪽부터 입력이 들어오니 왼쪽이 비어있다면 왼쪽자식, 아니라면 오른쪽 자식
		!tree[a].left ? tree[a].left = &tree[b] : tree[a].right = &tree[b];
		tree[b].costToParent = c;
	}
    
	cal(&tree[1]);

	cout << ans << endl;
}