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
sys.setrecursionlimit(10000)
def input():
    return sys.stdin.readline().rstrip()

def cycle_check(node,parent):
    if visited[node]:
        return node
    else:
        visited[node] = True
        for next_node in graph[node]:
            if next_node == parent:continue
            return_node = cycle_check(next_node,node)
            if return_node > 0:
                cycle_check_node[node] = True
                if return_node == node:
                    return 0
                else:
                    return return_node
        cycle_check_node[node] = False
        return 0
def dfs(start):
    stack = [(start,0,0)]
    visited = [True for _ in range(N+1)]
    while stack:
        node,parent,dis = stack.pop()

        if cycle_check_node[node]:
            distance[start] = dis
            return
        visited[node] = False

        for next_node in graph[node]:
            if next_node == parent:continue
            if visited[next_node]:
                stack.append((next_node,node,dis+1))



N = int(input())

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

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


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

cycle_check(1,0)


for k in range(1,N+1):
    if not cycle_check_node[k]:
        dfs(k)


print(*distance[1:])

  처음 풀이는 생각나는대로 풀었다. 먼저 2가지 함수로 나눠서 했다.

처음은 cycle을 체크하는 함수이다. 어느 노드에서든지 시작을 해서, 한번 방문을 했던 노드가 나올때까지

부모노드를 제외한 자식노드를 탐색해간다. 그러다보면 cycle의 시작지점을 방문하게 되는데 이때,

우리는 해당 node의 번호를 리턴해준다. 그러면 우리는 return 된 값이 0보다 크면

이 노드는 사이클에 포함된 노드임을 알 수 있다. 그러므로 return이 된 값이 0보다 크면 cycle임을 체크해주고,

시작지점에 도착하면, return 된 node와 값이 같으므로, 그걸로 판별뒤, 그 뒤에는 0을 반환해주면 된다.

그러면 우리는 0이 반환이 되면, 해당 노드는 사이클이 아닌것을 알게 된다.

이렇게 cycle을 체크한 뒤에

dfs를 돌려 cycle을 최초로 만나는 지점까지의 거리를 구해서 저장해주면 된다.

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

def cycle_check(node,parent):
    if visited[node]:
        return node
    else:
        visited[node] = True
        for next_node in graph[node]:
            if next_node == parent:continue
            return_node = cycle_check(next_node,node)
            if return_node > 0:
                cycle_check_node[node] = True
                distance[node] = 0
                if return_node == node:
                    return 0
                else:
                    return return_node
        cycle_check_node[node] = False
        return 0
def dfs(start,parent):
    if distance[start] != INF:
        return distance[start]
    for next_node in graph[start]:
        if next_node == parent:continue
        distance[start] = min(dfs(next_node,start)+1,distance[start])

    return distance[start]

    



N = int(input())

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

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


visited = [False for _ in range(N+1)]
cycle_check_node = [False for _ in range(N+1)]
INF = float('inf')
distance = [INF for _ in range(N+1)]

cycle_check(1,0)

for k in range(1,N+1):
    if not cycle_check_node[k] and distance[k] == INF:
        dfs(k,0)

print(*distance[1:])

이 방식은 좀 더 깔끔한 코드이다. 모든 노드들을 dfs를 각각돌리는것이 아닌. cycle인 부분에서부터 1씩 거리를 늘리면서 하나씩 해주는 방식이다.

이 방식이 좀 더 깔끔한 방식이다.

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
from collections import deque
input = sys.stdin.readline

def bfs(x,y):

    queue = deque()
    queue.append((x,y))
    visited[x][y] = False
    while queue:
        x,y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if visited[nx][ny] and arr[nx][ny] >= T:
                    visited[nx][ny] = False
                    queue.append((nx,ny))


N,M = map(int,input().split())

arr = []

for x in range(N):
    input_list = list(map(int,input().split()))
    temp = []
    for k in range(M):
        temp.append(sum(input_list[3*k:3*(k+1)]))

    arr.append(temp)

T = int(input())

T = 3*T


visited = [[True for _ in range(M)] for _ in range(N)]

dx = [-1,1,0,0]
dy = [0,0,-1,1]

cnt = 0
for x in range(N):
    for y in range(M):
        if arr[x][y] >= T  and visited[x][y]:
            bfs(x,y)
            cnt += 1

print(cnt)

이 문제는 처음들어올때부터 값을 계산해주는 방식으로 했다.

이 문제를 평균값을 구하면 float 값이 나올것 같아서, 어차피 문제에서 경계값이 정수이고,

한 픽셀을 구성하는 것은 3개로 고정적이므로 처음에 들어올때 열을 기준으로 3개씩 짤라주면서 그때의 합을 전부 저장하는 방식으로 했다.

이렇게 변형햔 배열을 가지고 BFS를 하면 되는데

계산의 편의성을 위해 경계값이 들어오자마자 그냥 3배를 해주었다.

그리고 난뒤에는 일반적인 BFS,DFS를 해주면 되는 문제이다.

방문을 하지않고, 경계값을 넘는 위치에 대해 bfs를 해서 인접한 픽셀들을 구하고, 함수가 끝난뒤에 개수를 늘려주었다.

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님 풀이를 복기한 것이다.

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

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

from collections import deque
import sys

R,C,T = map(int,input().split())


arr = []
start = []
for x in range(R):
    temp = list(input())

    for y in range(C):
        if temp[y] == 'G':
            start = (x,y)

    arr.append(temp)


stack = []

stack.append((*start,0,set()))
time = 0
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
while time<T:
    new_stack = []
    for x,y,eat,visited in stack:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx<R and 0<=ny<C:
                if arr[nx][ny] == 'S' and (nx,ny) not in visited:
                    new_visited = set()
                    new_visited.add((nx,ny))
                    new_visited = new_visited | visited
                    new_stack.append((nx,ny,eat+1,new_visited))
                    result = max(eat+1,result)
                elif arr[nx][ny] != '#':
                    new_stack.append((nx,ny,eat,visited))
    stack = [row[:] for row in new_stack]
    time += 1

print(result)
    

대회때 풀었던 풀이는 다음과 같다 BFS를 해주면서, 모든 이동경로를 누적해줬다.

그리고 visited에 없는 경우에만 고구마를 먹도록 해줬다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
def dfs(node,time,eat):
    global T,result,R,C
    if time == T:
        result = max(result,eat)
        return
    else:
        result = max(result,eat)
        for i in range(4):
            nx = node[0] + dx[i]
            ny = node[1] + dy[i]
            if 0<=nx<R and 0<=ny<C and not vistied[nx][ny]:
                vistied[nx][ny] = True
                if arr[nx][ny] == 'S':
                    dfs((nx,ny),time+1,eat+1)
                else:
                    dfs((nx,ny),time+1,eat)
                vistied[nx][ny] = False
            elif 0<=nx<R and 0<=ny<C and vistied[nx][ny] and arr[nx][ny] !='#':
                dfs((nx,ny),time+1,eat)

R,C,T = map(int,input().split())
result = 0
vistied = [[False for _ in range(C)] for _ in range(R)]


arr = []
start = []
for x in range(R):
    temp = list(input())
    for y in range(C):
        if temp[y] == '#':
            vistied[x][y] = True
        elif temp[y] == 'G':
            start = (x,y)
    arr.append(temp)


dx = [-1,1,0,0]
dy = [0,0,-1,1]

dfs(start,0,0)
print(result)

대회가 끝나고 난뒤의 풀이이다.

dfs를 해주는데 바문을 최초로 한 경우의 S일때에만 고구마를 먹도록 했다.

그리고, 방문을 했지만, 벽만 아니라면, 지나갈수 있도록 만들어줬다.

import sys

sys.setrecursionlimit(100000)


def dfs(x,y):
    if visited[x][y]:
        return INF
    elif dp[x][y] >0:
        return dp[x][y]
    else:
        visited[x][y] = True
        for i in range(4):
            nx = x + dx[i]*int(arr[x][y])
            ny = y + dy[i]*int(arr[x][y])
            if 0<=nx<N and 0<=ny<M and arr[nx][ny].isdigit():
                dp[x][y] = max(dp[x][y],dfs(nx,ny) + 1)
                if dp[x][y] == INF:
                    return INF
        visited[x][y] = False
    return dp[x][y]

            





dx = [-1,1,0,0]
dy = [0,0,1,-1]
N,M = map(int,input().split())
INF = float('inf')
arr = [list(input()) for _ in range(N)]
visited = [[False for _ in range(M)] for _ in range(N)]
dp = [[0 for _ in range(M)] for _ in range(N)]



result = dfs(0,0)

if result == INF:
    print(-1)
else:
    print(result+1)

 DP와 DFS를 활용한 문제 였다. 이 와 비슷한 문제를 풀어본 경험이 있었기 때문에 수월하게 풀 수 있었다.

여기서 문제에서 동전을 무한번 움직일때 -1을 출력한다는 것은 한번 방문을 했던 곳을 재귀 중에 방문을 하면, 들렸던 

장소에서 현재까지 오는 것이기때문에, 무한번 반복할 수 있다는 생각으로 만들어줬다.

그리고 입력과 똑같은 크기의 DP를 만들어서 해당 값이 초기값인 0이 아닌 다른 값이 있는 것은 해당 위치에서

탐색을 끝낸 것이기 때문에 초기값이 아닐때에는 바로 넘겨주는 것을 구현을 했다.

기본적이 풀이 방식은 다음과 같다.

왼쪽 위에서부터 탐색을 하면서, DFS를 처음 들어갈때 방문을 한곳인지 아닌지를 체크한다. 방문을 안한 곳이면,

방문을 체크해주고, 현재 위치에서 동서남북으로, 움직임이 가능한 경우를 탐색한다.

그리고 가능할때 그 방향으로 DFS를 하면서 한번 움직인 것이기 때문에 + 1을 해준다.

이렇게 재귀를 하면서 현재의 DP값과 최대값을 비교해서 저장을 해준다.

그리고 이 4방향을 다 둘러본것은 전부 탐색을 한 것이기 때문에 방문을 초기화 해준다.

그리고 현재 DP 값을 돌려주면 된다.

이렇듯 방문을 체크하는 리스트와 현재 위치에서의 최대값을 저장해주는 DP를 활용해서 풀 수 있는 문제였다.

import math
import sys


def dfs(node):
    stack = [(node,0,0)]
    visited = [True]*(N+1)
    distance = 0
    max_node = -1
    min_time = float('inf')
    visited[node] = False
    while stack:
        node,dis,time = stack.pop()
        if dis > distance:
            distance = dis
            max_node = node
            min_time = time
        elif dis == distance and min_time > time:
            max_node = node
            min_time = time

        for next_node in graph[node]:
            if visited[next_node]:
                new_dis = dis + 1
                new_time = time + graph[node][next_node]
                visited[next_node] = False
                stack.append((next_node,new_dis,new_time))

    return [max_node,distance,min_time]



input = sys.stdin.readline

N,T = map(int,input().split())


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


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

far_node_info = dfs(1)

result = dfs(far_node_info[0])


print(math.ceil(result[2]/T))

트리의 지름 이 문제를 풀어보면 해당 문제를 좀 더 쉽게 풀 수 있다.

문제의 조건은 총 2가지이다. 문제를 가장 많이 풀어야하며, 그 푸는데 시간이 가장 짧아야한다.

이 문제는 트리구조이다. 그래서 문제를 가장 많이 푼다는 것은 트리의 지름을 구하는것과 같다.

그러므로 처음 dfs로 아무 노드에서 가장 먼 노드를 찾고, 그 노드에서 가장 먼 노드들을 찾으면 그게 트리의 지름이 된다.

이걸 응용해서, 첫 dfs로 가장 먼 노드 하나를 찾는다.

그리고 두번째 dfs로 찾은 가장 먼 노드를 기준으로, dfs를 돌려서 깊이가 가장 깊은 노드들을 찾는다. 그리고 그 중에서, 시간이 가장 짧은 것을 선택해주면 된다.

이 문제는 1967번 문제의 트리의 지름을 응용한 문제이고, 트리의 특성에 대해 알고 있으면 쉽게 풀 수 있었던 문제였지만,

처음에 트리의 지름에 대한 아이디어를 얻지 못해서 어려웠던 문제이다.