Coding 공부

import sys
sys.setrecursionlimit(3000)
def input():
    return sys.stdin.readline().rstrip()

def get_diameter():
    result = 0
    visited = [0 for _ in range(N)]
    def dfs(node,tag):
        nonlocal visited
        stack = [(node,0)]
        visited[node] += 1
        max_node = -1
        max_dis = 0
        while stack:
            node,dis = stack.pop()
            if dis>max_dis:
                max_dis = dis
                max_node = node
            for next_node in graph[node]:
                if visited[next_node] == tag:
                    visited[next_node] += 1
                    stack.append((next_node,dis + graph[node][next_node]))
        return [max_node,max_dis]
    for idx in range(N):
        if visited[idx] == 0:
            far_node,_ = dfs(idx,0)
            _,dis = dfs(far_node,1)
            result += dis

    return result
N = int(input())

graph = [{} for _ in range(N)]
origin_path = []
for _ in range(N-1):
    x,y,pay = map(int,input().split())
    if x>y:
        x,y = y,x
    graph[x][y] = pay
    graph[y][x] = pay
    origin_path.append((x,y,pay))

result = get_diameter()
cnt = 0
for x,y,pay in origin_path:
    del graph[x][y]
    del graph[y][x]

    result = max(result,get_diameter()+pay)
    graph[x][y] = pay
    graph[y][x] = pay
print(result)

이 문제를 푼 사람도 적어서 안 알려진 문제이지만, 좋은 문제라 생각되어 다른 것보다 우선순위를 두어 복기를 했다.

이 문제의 조건을 읽어보면 하나의 트리가 주어지고, 이 트리의 간선 중 하나를 제거 한뒤,

이 간선을 트리의 구조를 지키면서, 간선을 추가해야하는 문제이다.

처음에 생각한 방법은, 트리의 간선을 제거하고, 임의의 두 노드를 뽑아서, 연결이 되어있지않다면 연결을 해주고,

cycle이나, 모든 노드를 통과하지 못하는 경우를 체크해주고, 트리의 지름을 구하는 식으로 생각을 했다.

하지만 이 방법은 2000C2 * 1999 * 트리의 지름을 구하는 복잡도가 되어 시간 초과가 날거라 생각을 했다.

이 문제를 푼 아이디어는 다음과 같다.

우리는 처음에 하나의 트리가 주어진다.

이 트리의 간선을 하나를 제거한다는 것은

2개의 트리가 된다는 것이다.

즉

이 와 같은 트리가 주어진다고 하면, 

하나의 간선을 없앤다는 것은 두개의 트리로 나뉘어진다는 것으로 볼수 있다.

우리는 이렇게 2개로 나뉘어진 트리를 이어주고, 트리의 지름을 최대로 구할려고 하는 것이다.

즉, 어느 노드 끼리 이어지는 것은 중요하지 않고, 2개의 트리를 연결했을때, 트리의 지름이 최대가 될려고 하는 것이다.

그러면 우리가 구하는 방법은 명확해진다 우리는 잘랐던 간선의 가중치를 그대로 연결한다.

그렇다하면, 2개의 트리의 어느 부분을 이었을때 가장 큰 트리의 지름이 될것인지 생각해보면,

명확하다. 2개의 트리에서 각각 지름을 구성하는 노드들의 끝점들을 이어주면 지름의 최대값이 될것이다.

즉 우리는 간선을 삭제하고, 나온 트리의 지름들을 각각 구한뒤, 자른 간선의 가중치를 더해주면

해당 간선을 삭제하고 연결했을때의 최대 트리의 지름을 구할 수 있게 된다.

그러면 이 방식은 간선의 개수 만큼 4번의 dfs를 하면 정답을 구할수 있게 된다.

여기서 나는, 2개로 나뉜 트리를 구분하기 위해, visited의 방문 회수를 기점으로, 언제 방문했는지를 구분해주었다.

이 문제는 처음에 푼 사람의 수가 워낙적고, 골1이라고 책정된 난이도 때문에 풀기 어려워보였지만,

문제에서 계속 강조하는 트리의 지름과 트리라는 구조라는 점에 착안해서 풀수 있었던 좋은 문제였다.

import sys
from itertools import combinations
import math
def input():
    return sys.stdin.readline().rstrip()



N = int(input())

graph = [[] for _ in range(N+1)]


for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

d_cnt = 0
g_cnt = 0


for i in range(1,N+1):
    if len(graph[i])>=3:
        k = len(graph[i])
        cnt = math.factorial(k)/(math.factorial(3)*math.factorial(k-3))
        g_cnt += cnt
    if len(graph[i])>=2:
        for next_node in graph[i]:
            if len(graph[next_node])>=2:
                a = len(graph[i]) - 1
                b = len(graph[next_node]) - 1
                d_cnt += (a*b)

d_cnt//=2

if d_cnt > g_cnt*3:
    print('D')
elif d_cnt < g_cnt*3:
    print('G')
else:
    print('DUDUDUNGA')

ㅈ 을 그리는 방법은 해당 노드를 기준으로 자식노드가 3개이상이면 구할수 있따. 그러므로 자식노드 중 3개를 고르는 경우의 수를 더해주면 된다.

ㄷ을 그리는 방법은 다음과 같다. 서로 연결된 두 노드의 자식노드가 2개이상이어야할때이다.

왜냐하면 서로 연결이 되어 있으므로, 하나는 빼고 서로 다른 노드들의 개수를 곱해주면 된다.

import sys

def input():
    return sys.stdin.readline().rstrip()

def nC3(n):
    return (n*(n-1)*(n-2))//6

N = int(input())

graph_node_cnt = [0 for _ in range(N+1)]
edge_list = []
for _ in range(N-1):
    x,y = map(int,input().split())
    graph_node_cnt[x] += 1
    graph_node_cnt[y] += 1
    edge_list.append((x,y))

g_cnt = 0
d_cnt = 0
for node in range(1,N+1):
    if graph_node_cnt[node] >=3:
        g_cnt += nC3(graph_node_cnt[node])

for x,y in edge_list:
    if graph_node_cnt[x]>=2 and graph_node_cnt[y]>=2:
        d_cnt += (graph_node_cnt[x]-1)*(graph_node_cnt[y]-1)


if d_cnt>3*g_cnt:
    print('D')
elif d_cnt < 3*g_cnt:
    print('G')
else:
    print('DUDUDUNGA')

이건 팩토리얼 대신 사용한 것이다.

import sys
sys.setrecursionlimit(123456)
def dfs(node):
    if not graph[node]:
        if pet_list[node]>0:
            return pet_list[node]
        return 0 
    else:
        temp = 0
        for child_node in graph[node]:
            temp += dfs(child_node)
        temp += pet_list[node]
        if temp <0:
            temp = 0
        return temp

def input():
    return sys.stdin.readline().rstrip()
N = int(input())

graph = [[] for _ in range(N+1)]
pet_list = [0 for _ in range(N+1)]
for i in range(2,N+1):
    pet,*arg = input().split()
    pay,island = map(int,arg)
    if pet == 'S':
        pet_list[i] = pay
        graph[island].append(i)
    else:
        pet_list[i] = -pay
        graph[island].append(i)




print(dfs(1))

이 문제는 기본적인 트리 문제였다. 그래프의 경로와 각 양과 늑대를 양수와 음수로 각각 매칭을 했다.

그리고 재귀를 통해서 리프노드까지 간 뒤에 양수이면 양수를 음수이면 0을 보내줬다.

그리고 그렇게 return 된 값들을 전부 더한뒤에

현재 아일랜드의 값을 더해주고, 그 값이 0미만이 되면 0으로 보내주고 그게 아니면 원래대로 보내주면 풀리는 문제이다.

import sys
from collections import defaultdict,deque
def input():
    return sys.stdin.readline().rstrip()


N = int(input())

graph = defaultdict(list)
pet_list = [0 for _ in range(N+1)]
parents = [0 for _ in range(N+1)]
for next_node in range(2,N+1):
    pet,*arg = input().split()
    pay,island = map(int,arg)
    if pet == 'S':
        pet_list[next_node] = pay
    else:
        pet_list[next_node] = -pay
    graph[island].append(next_node)
    parents[next_node] = island

que = deque()
que.append(1)
stack = []
while que:
    cur_node = que.popleft()
    stack.append(cur_node)
    for next_node in graph[cur_node]:
        que.append(next_node)

while stack:
    cur_node = stack.pop()
    pet_list[parents[cur_node]] += max(0,pet_list[cur_node])

print(pet_list[0])

재귀를 이용하지 않고 푸는 방법이다.

먼저 bfs로 탐색하면서 그 순서를 stack에 넣어주고, 끝에서부터 하나씩 꺼내주면 된다.

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()


def dfs(cur_idx,parent_idx):
    global cnt
    depth[cur_idx] = depth[parent_idx] + 1


    if tree[cur_idx][0] != -1:
        dfs(tree[cur_idx][0],cur_idx)
    cnt += 1
    width[depth[cur_idx]].append(cnt) 
    if tree[cur_idx][1] != -1:
        dfs(tree[cur_idx][1],cur_idx)

N = int(input())
root_check = [0 for _ in range(N+1)]
tree = [[-1 -1] for _ in range(N+1)]
depth = [0 for _ in range(N+1)]
width = defaultdict(list)
for _ in range(N):
    x,left_node,right_node = map(int,input().split())
    tree[x] = [left_node,right_node]
    if left_node != -1:
        root_check[left_node] += 1
    if right_node != -1:
        root_check[right_node] += 1
root_num = -1
for k in range(1,N+1):
    if root_check[k] == 0:
        root_num = k
        break


cnt = 0
dfs(root_num,0)

max_value = 0
max_depth = -1
for d in range(1,max(depth)+1):
    max_width,min_width = max(width[d]),min(width[d])
    if max_value < max_width - min_width + 1:
        max_value = max_width - min_width + 1
        max_depth = d

print(max_depth,max_value)

이 문제를 풀때 주의할점은 2가지이다.

루트노드가 꼭 1인것은 아니다.

들어오는 순서가 1,2,3,4,5,6,7,8,....N이 아닐수도 있다.

이 2가지를 주의하면 풀면 되는 문제이다.

먼저 트리를 위한 (N+1)*2의 배열을 만들어뒀다.

각 행의 0번인덱스는 왼쪽 자식, 1번인덱스는 오른쪽자식을 의미한다.

이 문제는 중위순회를 구현을 해서, 왼쪽 자식->루트->오른쪽자식 순서로 탐색을 해준다.

그리고 루트일때 현재의 LEVEL에 width를 저장을 해주엇다.

cnt를 0부터 시작했기때문에, append 하기 직전에 +=1 을 해준것이다.

만약 1부터 하신분들은 순서를 바꾸면될것이다.

그리고 전체 레벨 만큼 탐색을하면서 최대 너비를 구해주면 되는 문제이다.

좀 더 깔끔히 하신분들은 level별로 2차원배열을 만든뒤에 둘 중 하나는 최대값 하나는 최소값을 저장을 시켜서 

마지막에 바로 계산이 가능하게 한 분들도 계신다.

import sys
sys.setrecursionlimit(20000)
def input():
    return sys.stdin.readline().rstrip()
def trace(cur_node,prev_check):
    visited[cur_node] = False
    flag = 0
    if not prev_check:
        if dp[cur_node][0] < dp[cur_node][1]:
            result.append(cur_node)
            flag = 1
    for next_node in graph[cur_node]:
        if visited[next_node]:
            trace(next_node,flag)

def dfs(node):
    visited[node] = False
    child_node = []
    for next_node in graph[node]:
        if visited[next_node]:
            child_node.append(next_node)
    if not len(child_node):
        dp[node][1] = arr[node]

        return
    else:
        dp[node][1] += arr[node]
        for child in child_node:
            dfs(child)
            dp[node][0] += max(dp[child][1],dp[child][0])
            dp[node][1] += dp[child][0]



N = int(input())
arr = [0] + list(map(int,input().split()))

# 1이 선택 
# 0이 선택 x
dp = [[0 for _ in range(2)] for _ in range(N+1)]

graph = [[] for _ in range(N+1)]
visited = [True for _ in range(N+1)]
for k in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)


dfs(1)

print(max(dp[1]))


result = []
visited = [True for _ in range(N+1)]
trace(1,0)
result.sort()
print(*result)

어려웠던 문제였다. 트리dp를 활용해서 최적의 경우를 찾는 것은 많았지만, 그 최적을 만족하는 것을 trace를 하는 문제는 처음이라 푸는데 오래걸렸다.

dp라는 테이블을 만들고 (N+1)*2의 배열을 만들어 두었다.

여기서 1은 해당 노드를 선택했을때의 최대값

0은 해당 노드를 선택하지 않았을때의 최대값이다.

만약 리프노드이면 자신을 선택하는 조건이외에는 없을것이다.

그러므로 dp[leef_node][1] = arr[leef_node]를 넣어준다.

리프노드를 제외한 나머지 노드들은 0번 인덱스와 1번인덱스의 최대값을 구해야한다.

현재 노드를 선택했을때 즉 1번인덱스에는

현재 노드를 cur_node라고 했을때 arr[cur_node]를 더해줘야할것이다.

그리고 현재 노드를 선택했으므로, 자식노드들은 선택을 하지 못한다.

그러므로 dp[cur_node][1] += dp[child_node][0] 와 같이

자식 노드들의 선택하지않았을때의 값들을 전부 더해줘야한다.

그리고 현재 노드를 선택하지 않았을때에는

자식 노드를 선택하던지, 선택하지 않는것은 마음대로 할 수 있다.

그러므로 둘중 더 큰 값을 더해주면 된다.

이렇게 dp에 값을 누적시켜서 구하면

우리는 1번노드로 시작했기 때문에

1번노드의 dp에서 최대값을 구할 수 있다.

그러면 우리는 이 dp에서 어떤 노드들이 선택됬는지를 찾아봐야한다.

우리는 이전 노드에서 선택했는지 안했는지에 따라, 현재 노드를 선택할수 있는지 아닌지가 결정이 된다.

그래서 우리는 prev_check를 통해 문제를 해결했다. 위와 동일하게 하기 위해서 0일때에는 부모노드를 선택하지 않았다.

1일때에는 부모노드를 선택했다이다.

만약 부모노드를 선택하지 않았을때에는, 우리는 지금 있는 현재노드를 선택할지 안할지를 결정지을수 있다.

그 결정방법은 dp에 저장된 값을 비교를 해서, 우리가 선택하지 않았을때보다 선택했을때의 값이 더 크면,

그때 현재노드를 선택을 하고, flag를 1로 바꿔준다. 현재노드를 선택을 했으므로, result에 추가 시켜준다.

그리고 재귀를 통해 모든 노드들에 대해 탐색을 해주면 된다.

이 문제는 최대값을 구하는 것 뿐만 아니라, 그 경우의 수가 만들어지는 것을 찾는데 더 어려움을 겪었다.

트리 dp와 관련된 문제들을 좀 더 연습해야겠다.

import sys
sys.setrecursionlimit(10000)
def input():
    return sys.stdin.readline().rstrip()


def LCS(X,Y):
    if depth[X] != depth[Y]:
        if depth[X]>depth[Y]:
            X,Y = Y,X
        for i in range(MAX_NODE-1,-1,-1):
            if (depth[Y]-depth[X] >= (1<<i)):
                Y = parents[Y][i]
    if X == Y:
        return X
    if (Y != X):
        for i in range(MAX_NODE-1,-1,-1):
            if parents[X][i] != parents[Y][i]:
                X = parents[X][i]
                Y = parents[Y][i]
    return parents[X][0]
def tree_make(idx,cur_node,node_cnt,parent_idx):
    if idx == len(binary_list):
        return
    if binary_list[idx] == 0:
        node_cnt += 1
        cur_node = node_cnt
        binary_search[idx+1] = cur_node
        tree[cur_node].visited.append(idx+1)
        tree[cur_node].parent = parent_idx
        depth[cur_node] = depth[parent_idx] + 1
        parents[cur_node][0] = parent_idx
        if cur_node != 1:
            parent_node = tree[cur_node].parent
            if tree[parent_node].left == None:
                tree[parent_node].left = cur_node
            else:
                tree[parent_node].right = cur_node
        tree_make(idx+1,cur_node,node_cnt,cur_node)
    else:
        binary_search[idx+1] = cur_node
        tree[cur_node].visited.append(idx+1)
        cur_node = tree[cur_node].parent
        tree_make(idx+1,cur_node,node_cnt,cur_node)



class Node():
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
        self.parent = None
        self.visited = []

N = int(input())
binary_list = list(map(int,list(input())))
i,j = map(int,input().split())
tree = [Node(i) for i in range(N+1)]
MAX_NODE = 15
binary_search = [0 for _ in range(len(binary_list)+1)]
depth = [0 for _ in range(N+1)]
parents = [[0 for _ in range(MAX_NODE)] for _ in range(N+1)]

tree_make(0,0,0,0)
for par_idx in range(1,MAX_NODE):
    for k in range(1,N+1):
        parents[k][par_idx] = parents[parents[k][par_idx-1]][par_idx-1]

X,Y = binary_search[i],binary_search[j]

result_node = LCS(X,Y)
print(*tree[result_node].visited)

LCA를 이용해서 풀어본 처음 문제였다.

LCA를 공부하면서 푼 풀이이다. 

LCA에 대한 자세한 설명은

https://jason9319.tistory.com/90    https://www.crocus.co.kr/660    https://m.blog.naver.com/kks227/220820773477  https://velog.io/@lre12/LCA-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Lowest-Common-Ancestor

위의 사이트들을 참조하길 바란다.

LCA를 공부하면서, 이해하다가 막혔다가 푼 부분을 적으면 다음과 같다.

1. 부모를 저장하는 dp 테이블에는 해당 노드의 모든 부모를 저장하는 것이 아닌 2^k번째 부모들만 압축해서 저장해놓는것이다.

2. 위의 파생이지만, 그렇기 때문에, 두 높이의 차이가 1<<i 즉 2^i 차이가 나면, i만큼 올려주면 되는것이다.

3. 그리고 두 높이가 같고, 서로 다르다면, k번째 위치부터 다른 값까지 한꺼번에 올려버린다.

  즉, dp[node1][k] , dp[node2][k] 는 다르지만, dp[node1][k+1], dp[node][k+1]이 같으면

   각 노드들의 2^k + 1 ~ 2^(k+1) 사이에 최소 공통 조상이 있을 것이다. 이 부분을 주의하면 된다.

4. 또한, 첫번째에서 말한것처럼 2^k번째 만 저장을 시켜놓은것이기때문에

    2^(k+1) = 2^k + 2^k 이다.

    2^k = 2^(k-1) + 2^(k-1) 이므로,

dp[node][k] = dp[ dp[node][k-1] ] [k-1] 으로 하면 LCA의 해당 노드들의 모든 공통조상부모에 대해서 저장시킬수 있다.

위의 것들이 윗 링크들을 공부하면서 제가 깨달은 부분이다.

인제는 문제로 돌아가서 

여기서 문제에 주어진 비트를 트리구조로만 바꾸면 우리는 위에서 배운 LCA를 적용시키면 된다.

저는 여기서 이 문제를 해결하기 위해 Node라는 클래스를 만들어놨습니다.

해당 Node에는 총 5가지의 파라미터가 있습니다.

data는 이 노드의 번호를 나타내고,

left는 왼쪽 자식번호

right는 오른쪽 자식번호

parent는 부모 번호

visited는 우리가 주어진 비트에서 몇번재 비트에서 이 노드를 방문했는지 표시르 위한 것입니다.

저는 tree_make라는 재귀함수를 만들어 이 문제를 해결했습니다.

입력 parameter는 4가지가 있고, idx는 현재 입력으로 주어진 비트의 몇번째 idx인지를 나타냅니다.

cur_node는 현재 노드의 번호입니다.

node_cnt는 지금까지 생성된 노드의 개수입니다.

parent_idx는 부모 노드의 번호입니다.

비트에서 우리가 0을 만나면 최초로 생성되는 노드로 진입하게 되는겁니다.

그래서 node_cnt를 1을 늘려주고, cur_node를 node_cnt로 바꿔줍니다.

그러면 우리는 현재 부모노드의 정보를 알고 있으므로,

부모노드의 left와 right 중 빈 순서대로 넣어주면 됩니다.

그리고 1을 만나게 되면 우리는 현재 방문하고 있던 노드에서 다시 되돌아가서 부모노드로 가야합니다.

그렇기 때문에 cur_node를 부모노드로 치환시키고, 재귀를 반복하면 됩니다.

즉 0을 만나면 새로운 노드가 생성이되고,

1을 만나면 부모노드로 되돌아간다는 점만 기억을 하면, 문제에서 주어진 비트를 트리로 만들 수 있습니다.

코드가 깔끔하지 못해, 다른 분들의 코드를 보는 것을 더 추천합니다.

위와 같은 작업을 해서 비트를 트리구조로 바꾼뒤에 LCA을 적용시키면 이 문제를 해결 할 수 있습니다.

LCA와 관련된 문제를 처음 풀어보았기에, 헷갈리던 점도 많았고, 트리에 대해 숙달되지 못했기에,

비트를 트리로 구현하는데에 오래 걸린 문제였습니다.

매번 트리와 관련된 문제가 나오면 문제를 해결하는데 시간이 오래걸리는 것 같은데,

이 부분을 숙달하는데 더 노력을 해야할 것 같습니다.

import sys
input = sys.stdin.readline
def dfs(node):
    global result 
    if not len(graph[node]):
        ball_cnt_list[parent_list[node]] += (ball_cnt_list[node] -1)
        result += abs(ball_cnt_list[node] - 1)
    else:
        for next_node in graph[node]:
            dfs(next_node) 
        if parent_list[node] != -1:
            ball_cnt_list[parent_list[node]] += ball_cnt_list[node] - 1
            result += abs(ball_cnt_list[node] - 1)



while True:
    N = int(input())

    if N == 0:
        break
    graph = [[] for _ in range(N+1)]
    parent_list = [-1 for _ in range(N+1)]
    ball_cnt_list = [0 for _ in range(N+1)]
    indegree = [0 for _ in range(N+1)]
    for _ in range(N):
        node_num,ball_cnt,*arg = map(int,input().split())
        if arg[0]>0:
            for child_node in arg[1:]:
                graph[node_num].append(child_node)
                parent_list[child_node] = node_num
                indegree[child_node] += 1
        ball_cnt_list[node_num] = ball_cnt

    result = 0
    for k in range(1,N+1):
        if indegree[k] == 0:
            dfs(k)
    print(result)

 이 문제를 해결하는데 어려움을 겪었다.

이 문제를 해결하는 방식은 가장 끝 리프노드부터 1씩 무조건 맞춰주는 것이다.

그리고 그때의 절대값들을 전부 더해주는 방식을 해주면 된다.

현재 노드에서 1와의 차이를 부모노드로 옮겨주고,

그때 차이의 절대값을 결과에 계속 더해주면 된다.

# dotorya님 풀이

import sys
input = sys.stdin.readline
def dfs(node):
    global result 
    cnt = ball_cnt_list[node] -1

    for next_node in graph[node]:
        cnt += dfs(next_node)

    result += abs(cnt)
    return cnt



while True:
    N = int(input())

    if N == 0:
        break
    graph = [[] for _ in range(N+1)]
    ball_cnt_list = [0 for _ in range(N+1)]
    indegree = [0 for _ in range(N+1)]
    for _ in range(N):
        node_num,ball_cnt,*arg = map(int,input().split())
        if arg[0]>0:
            for child_node in arg[1:]:
                graph[node_num].append(child_node)
                indegree[child_node] += 1
        ball_cnt_list[node_num] = ball_cnt

    result = 0
    for k in range(1,N+1):
        if indegree[k] == 0:
            dfs(k)
    print(result)

두 번째 풀이는 dotorya님 풀이를 복기한 것이다.

끝노드부터 하는 것은 동일하다.

그리고 현재의 격차를 상위노드로 전달해주고, 결과에는 그 절대값을 계속 누적해서 더해주면 되는 것이다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)
def root_dfs(node):
    if visited[node]:
        return
    visited[node] = True
    child_list = []
    for next_node in tree[node]:
        if not visited[next_node]:
            child_list.append(next_node)

    if len(child_list)==2:
        return [node,0]
    elif len(child_list) == 1:
        return_value = root_dfs(child_list[0])
        return_value[1] += tree[node][child_list[0]]
        return return_value
    else:
        return [node,0]

def leef_dfs(node):
    if visited[node]:
        return
    visited[node] = True
    child_list = []
    for next_node in tree[node]:
        if not visited[next_node]:
            child_list.append(next_node)
    
    if len(child_list)==0:
        return 0
    else:
        result = 0
        for child_node in child_list:
            result = max(result,leef_dfs(child_node)+tree[node][child_node])
        return result
N,R = map(int,input().split())
tree = [{} for _ in range(N+1)]
for _ in range(N-1):
    x,y,b = map(int,input().split())
    tree[x][y] = b
    tree[y][x] = b


visited = [False for _ in range(N+1)]

root_node_info = root_dfs(R)
visited[root_node_info[0]] = False
leef_dis = leef_dfs(root_node_info[0])
print(root_node_info[1],leef_dis)

2개의 DFS로 나눠서 최초엔 풀었다.

첫번째 풀이는 두개로 나뉘어서 DFS를 했다.

첫 DFS는 기가노드를 찾는것이다. 기가노드를 찾으면 그때의 길이를 저장해놓는다.

그리고 기가노드에서 부터 리프노드까지 최대 길이를 찾아내는 방식으로 해서 구했다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(300000)
def root_dfs(node,dis):
    if visited[node]:
        return
    visited[node] = True
    count = 0
    nexts = -1
    distance = 0
    for next_node in tree[node]:
        if not visited[next_node]:
            count += 1
            nexts = next_node
            distance += tree[node][next_node]
    if count == 1:
        return root_dfs(nexts,dis+distance)
    else:
        return [node,dis]

def leaf_dfs(node,dis):
    global leef_dis
    visited[node] = True
    count = 0
    for next_node in tree[node]:
        if not visited[next_node]:
            leaf_dfs(next_node,dis+tree[node][next_node])
            count += 1
    if not count:
        leef_dis = max(leef_dis,dis)


N,R = map(int,input().split())
tree = [{} for _ in range(N+1)]
for _ in range(N-1):
    x,y,b = map(int,input().split())
    tree[x][y] = b
    tree[y][x] = b


visited = [False for _ in range(N+1)]
root_dis = root_dfs(R,0)
leef_dis = 0
leaf_dfs(root_dis[0],0)
print(root_dis[1],leef_dis)

두번째 풀이는 좀더 깔끔한 풀이이다.

count를 별도로 세주어서 기가노드인지 리프노드인지 구분을 해주었다.

기가노드가 아닐때에는 재귀를 해주면서 distance를 더해주고, 만약 기가노드일때는 재귀를 머추고, 기가노드의 위치와

지금까지 누적된 거리를 반환해준다.

leaf_dfs도 비슷한 과정을 겪는다.

leaf_dfs를 계속 재귀를 통해 가면서 leaf_node에 도착하면 현재까지 누적된 값과 최대값과 비교를 해서 더 큰 값을 넣어주면 된다.