첫번째는 트리의 모든 노드에 자신이 속한 서브트리의 번호를 지정해서 비교하는 방법입니다.

간선을 하나 자른다는 것은 서브트리가 하나 생긴다는 얘기라 두 노드를 비교할때 서브트리 번호로 비교하는 것이구요 그렇기 때문에 간선이 하나 잘릴 때마다 해당 노드가 루트노드로 포함되는 서브트리의 모든 노드들에게 다른 서브트리 번호를 부여하기 위해 전파되다보니 시간이 오래걸려서 시간초과난 것 같아요.

두번째는 단순하게 각 노드마다 부모노드의 번호를 가지게 해서, 간선으로 자를 경우 해당 노드는 부모가 없고 루트노드라 0을 넣는 방식으로했습니다. 이경우 자르는 건 빠르지만 반대로 두개를 비교할 때 서브트리의 루트노드까지 찾아가서 비교를 해야되기때문에 느려서 시간초과가 난 것 같아요

시간초과전까지 채점중 비율을 보면 1<2이기 때문에 2번이 더 빠르지만 2번마저도 7%에서 시간초과가 나버리네요....

더 빠르게 구현할 수 있는 방법이 있을까요?

문제 자체가 이진트리라는 조건은 없어서 자식 노드의 개수를 정해놓을 수 없어서 다른 방법을 생각해내기가 어렵네요..