https://www.acmicpc.net/problem/19535코드from math import combn = int(input())children = [0]*(n+1)graph = []for _ in range(n-1): u, v = map(int, input().split()) children[u] += 1 children[v] += 1 graph.append((u, v))d_num, g_num = 0, 0# ㄷfor u, v in graph: d_num += (children[u]-1)*(children[v]-1)# ㅈfor i in range(1, n+1): if children[i] >= 3: g_num += comb(children[i], 3)i..
트리
https://www.acmicpc.net/problem/20364코드from collections import dequeimport sysinput = sys.stdin.readlinen, q = map(int, input().split())dp = [-1]*(n+1) # dp[i]는 1번에서 i번까지 가는 길에 가장 처음 마주치는 점유된 땅 번호for i in range(q): want = int(input()) if dp[want] == -1: # 가는 길에 이미 점유된 땅이 없음 # 이 땅 아래로는 다 이 땅을 지나야만 한다고 표시 q = deque([want]) while q: now = q.popleft() ..
11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 코드 from collections import deque import sys input = sys.stdin.readline n = int(input()) graph = [[] for _ in range(n+1)] # 노드 간 연결 for _ in range(n-1): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) # 각 노드 레벨 구하기(BFS) level = [-1]*(n+..
3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 코드 from collections import deque import sys input = sys.stdin.readline for _ in range(int(input())): n = int(input()) parent = [-1]*(n+1) children = [[] for _ in range(n+1)] for _ in range(n-1): a, b = map(int, input().split()) par..
2233번: 사과나무 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 2,000)이 주어진다. 둘째 줄에는 벌레가 만드는 2×N자리의 이진수가 주어진다. 셋째 줄에는 썩은 사과의 위치를 나타내는 두 정수 X, Y가 주어진다. 이는 2×N자리 www.acmicpc.net 코드 import sys sys.setrecursionlimit(10**6) n = int(input()) binary = '9' + input() x, y = map(int, input().split()) parent = [[] for _ in range(n+1)] # 각 노드의 부모(가까운 노드부터) depth = [-1] * (n+1) # 각 노드의 깊이 removed = [] inout = [[] for _ in range(n+1)] de..
