Problem:


Score : 400 points

Problem Statement

Given is a tree G with N vertices.
The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i.

Consider painting the edges in G with some number of colors.
We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.

Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

Print N lines.

The first line should contain K, the number of colors used.

The (i+1)-th line (1 \le i \le N-1) should contain c_i, the integer representing the color of the i-th edge, where 1 \le c_i \le K must hold.

If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

8
1 2
2 3
2 4
2 5
4 7
5 6
6 8

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Runtime Error

Solution code:
#初期入力
import sys
input = sys.stdin.readline
import random
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            ={i:tuple() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i]=a,b             #色を出力するため

#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
color_vertex ={i:set() for i in range(1,N+1)} #辺につながっている頂点に使った色
color_side =[0]*(N-1)
color =0
color_all =set(j for j in range(1,color_max +1) )
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    #while True:
    color =(color_all - color_vertex[v_a] -color_vertex[v_b]).pop() #全ての色-使った色[a]-使った色[b]
    #if color not in color_vertex[A[i]] :  #使った色リストに入っているか？
    color_side[i] =color          #辺の色を出力用に決める（2行上の＋１）
    color_vertex[v_a].add(color)    #前の頂点に使った色として追加
    color_vertex[v_b].add(color)    #先の頂点に使った色として追加
          
        #    break
        #else:
         #   color +=1
    
#出力
print(color_max)
print(*color_side, sep="\n")

Submission status: Runtime Error

Solution code:
n=int(input())

#初期値が0の辞書
from collections import defaultdict
tree = defaultdict(lambda: set([])) 

color={}
key=[]

for _ in range(n-1):
    a,b=map(int,input().split())
    tree[a-1].add(b-1)
    tree[b-1].add(a-1)
    color[(a-1,b-1)]=0
    key.append((a-1,b-1))

checked=[0]*n
cnt=0

def DEF(parent_color,node_no):
    global color,checked,tree,cnt
    checked[node_no]=1
    cnt=max(cnt,parent_color)
    i=1
    print("node_no",node_no)
    for item in tree[node_no]:
        if checked[item]==0:
            if i==parent_color:
                i+=1
            
            color[(min(item,node_no),max(item,node_no))]=i
            DEF(i,item)
            i+=1
DEF(0,1)

print(cnt)
for item in key:
    print(color[item])

Submission status: Runtime Error

Solution code:
class Tree:
    def __init__(self, root):
        self.__root = root
        self.__children = {root: []}
        self.__parent = {root: -1}

    def get_root(self):
        return self.__root

    def get_children(self, node):
        return self.__children[node]

    def add_child(self, node, child):
        self.__children[node].append(child)
        self.__children[child] = []
        self.__parent[child] = node

    def get_parent(self, node):
        return self.__parent[node]


N = int(input())
tree = Tree(1)
input_list = []
li = []
for n in range(N - 1):
    a, b = map(int, input().split())
    input_list.append([a, b])
    try:
        tree.add_child(a, b)
    except:
        tree.add_child(b, a)

colors_dict = {}

def color(node, colors):
    children = tree.get_children(node)
    l = len(children)
    if l == 0:
        return colors
    if node == tree.get_root():
        for i in range(l):
            colors_dict[children[i]] = i + 1
            colors = max(colors, i + 1, color(children[i], colors))
        return colors
    col = 1
    i = 0
    while True:
        if i >= l:
            break
        if col == colors_dict[node]:
            col += 1
            continue
        colors_dict[children[i]] = col
        colors = max(colors, col, color(children[i], colors))
        i += 1
        col += 1
    return colors
colors = color(1, 0)
print(colors)
for edge in input_list:
    a, b = edge
    if tree.get_parent(b) == a:
        print(colors_dict[b])
    else:
        print(colors_dict[a])

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
N=int(input())

def dfs(u,par):
  col=1
  for v in graph[u]:
    if col==par:
      col+=1
    color_dic[(u,v)]=col
    dfs(v,col)
    col+=1

elist=[]
graph=[[] for _ in range(N+1)]
for _ in range(N-1):
  a,b=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b))
#print(graph)

color_dic={}
dfs(1,-1)
#print(color_dic)

K=len(set(color_dic.values()))
print(K)
for e in elist:
  print(color_dic[e])

Submission status: Runtime Error

Solution code:
n = int(input())
neighbors = [[] for i in range(n+1)]
ab = []
for i in range(n-1):
    line = list(map(int, input().split()))
    neighbors[line[0]].append(line[1])
    neighbors[line[1]].append(line[0])
    ab.append((line[0], line[1]))
maximum = 0
neighbors_max = 0
for i in range(n):
    if maximum < len(neighbors[i]):
        neighbors_max = i
        maximum = len(neighbors[i])
edgecolors = {}
reached = {neighbors_max}
def make_other_colors(c, m):
    res = []
    if c > m:
        res += [i+1 for i in range(m)]
    else:
        res += [i+1 for i in range(c-1)]
        res += [maximum-i for i in range(m-c+1)]
    return res
def coloring(v, c):
    if c == 0:
        reached.add(v)
        for i in range(len(neighbors[v])):
            edgecolors[(v, neighbors[v][i])] = i + 1
            edgecolors[(neighbors[v][i], v)] = i + 1
            reached.add(neighbors[v][i])
            coloring(neighbors[v][i], i+1)
        return
    l = len(neighbors[v])
    if l == 1 and neighbors[v][0] in reached:
        reached.add(v)
        return
    other_colors = make_other_colors(c, l-1)
    i = 0
    j = 0
    while i < l:
        if neighbors[v][i] in reached:
            i += 1
            continue
        edgecolors[(v, neighbors[v][i])] = other_colors[j]
        edgecolors[(neighbors[v][i], v)] = other_colors[j]
        reached.add(neighbors[v][i])
        coloring(neighbors[v][i], other_colors[j])
        i += 1
        j += 1
coloring(neighbors_max, 0)
print(maximum)
for i in ab:
    print(edgecolors[i])

Submission status: Runtime Error

Solution code:
n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].append([b,i])
ans = [None] * (n-1)

def dfs(now, color):
    cnt = 1
    for to, num in g[now]:
        if cnt == color:
            cnt += 1
        ans[num] = cnt
        dfs(to, cnt)
        cnt += 1
dfs(0, 0)
print(max(ans))
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
理解できないので後回し
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    # https://atcoder.jp/contests/abc146/tasks/abc146_d
    # https://qiita.com/drken/items/a803d4fc4a727e02f7ba#4-4-%E6%A0%B9%E3%81%AE%E3%81%AA%E3%81%84%E6%9C%A8%E3%81%AE%E8%B5%B0%E6%9F%BB
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        # G[頂点]に、(辺番号, 行き先)の情報を記入
        # 辺番号など不要で、行き先だけ記入すればいいこともある
        G[a - 1].append((i, b - 1))
        G[b - 1].append((i, a - 1))
    ans = [0] * (N - 1)

    # now_nd: 現在探索中の頂点、parent: now_ndの親(now_ndが根のときは - 1)。もうひとつの引数で調べたいものや持っておきたい情報をとる（ex. 深さ）。今回は親からそのノードへのびる辺の色pre_cl
    def dfs(G, now_nd, parent, pre_cl):
        cl = 1  # 1種類目

        for (num, nxt_nd) in G[now_nd]:
            if nxt_nd == parent:  # 逆流防止
                continue
            nxt_cl = cl  # 辺の色を指定
            if nxt_cl == pre_cl:  # かぶったら色変
                nxt_cl += 1
            ans[num] = nxt_cl
            dfs(G, nxt_nd, now_nd, nxt_cl)
            cl = nxt_cl + 1

    root = 0
    dfs(G, root, -1, -1)
    print(max(ans))
    for a in ans:
        print(a)


resolve()

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc146/tasks/abc146_d
# https://qiita.com/drken/items/a803d4fc4a727e02f7ba#4-4-%E6%A0%B9%E3%81%AE%E3%81%AA%E3%81%84%E6%9C%A8%E3%81%AE%E8%B5%B0%E6%9F%BB
N = int(input())
G = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    # G[頂点]に、(辺番号, 行き先)の情報を記入
    # 辺番号など不要で、行き先だけ記入すればいいこともある
    G[a - 1].append((i, b - 1))
    G[b - 1].append((i, a - 1))
ans = [0] * (N - 1)

# now_nd: 現在探索中の頂点、parent: now_ndの親(now_ndが根のときは - 1)。もうひとつの引数で調べたいものや持っておきたい情報をとる（ex. 深さ）。今回は親からそのノードへのびる辺の色pre_cl
def dfs(G, now_nd, parent, pre_cl):
    color = 1  # 1種類目

    for (num, nxt_nd) in G[now_nd]:
        if nxt_nd == parent:  # 逆流防止
            continue
        nxt_cl = color  # 辺の色を指定
        if nxt_cl == pre_cl:  # かぶったら色変
            nxt_cl += 1
        ans[num] = color
        dfs(G, nxt_nd, now_nd, nxt_cl) # G[now_nd]のnxt_ndがなくなったら、つまり葉まで調べ尽くしたら
        color = nxt_cl + 1  # 次の頂点で試す色。今使ったのとは違う種類

root = 0
dfs(G, root, -1, -1)
print(max(ans))
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

class Node:
    def __init__(self, num):
        self.num = num
        self.edge = []
        self.color = {}
    
    def ap_edge(self,e):
        self.edge.append(e)

    def rm_edge(self,e):
        self.edge.remove(e)
    
    def co_edge(self,n, c):
        self.color[n] = c




def solve(N: int, a: "List[int]", b: "List[int]"):
    nodes = [Node(num+1) for num in range(N)]

    for ai, bi in zip(a,b):
        nodes[ai-1].ap_edge(bi)
        nodes[bi-1].ap_edge(ai)

    def s_node(node_num, prev_c):
        el = nodes[node_num-1].edge
        # print("node_num:{} el:{}".format(node_num, el))
        if len(el)>0:
            if prev_c not in range(1,len(el)+1):
                c_list = range(1,len(el)+1)
            else:
                c_list = list(range(1,len(el)+2))
                c_list.pop(prev_c-1)
            
            # print("c_list:{} prev_c:{}".format(c_list, prev_c))

            for node_n, c_ in zip(el, c_list):
                # 親の頂点に対する処理
                nodes[node_num-1].co_edge(node_n, c_) # 子のエッジの色を持つ
                # 子の頂点に対する処理
                nodes[node_n-1].rm_edge(node_num) # 親のエッジを削除
                s_node(node_n, c_)

    s_node(1,0)


    ans = []
    for ai, bi in zip(a,b):
        if bi in nodes[ai-1].edge:
            ans.append(nodes[ai-1].color[bi])
        elif ai in nodes[bi-1].edge:
            ans.append(nodes[bi-1].color[ai])
        else:
            ans.append(0)
        

    print(max(ans))
    [print(c_) for c_ in ans]


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

class Node:
    def __init__(self, num):
        self.num = num
        self.edge = []
        self.color = {}
    
    def ap_edge(self,e):
        self.edge.append(e)

    def rm_edge(self,e):
        self.edge.remove(e)
    
    def co_edge(self,n, c):
        self.color[n] = c




def solve(N: int, a: "List[int]", b: "List[int]"):
    nodes = [Node(num+1) for num in range(N)]

    for ai, bi in zip(a,b):
        nodes[ai-1].ap_edge(bi)
        nodes[bi-1].ap_edge(ai)

    def s_node(node_num, prev_c):
        el = nodes[node_num-1].edge
        # print("node_num:{} el:{}".format(node_num, el))
        if len(el)>0:
            if prev_c not in range(1,len(el)+1):
                c_list = range(1,len(el)+1)
            else:
                c_list = list(range(1,len(el)+2))
                c_list.pop(prev_c-1)
            
            # print("c_list:{} prev_c:{}".format(c_list, prev_c))

            for node_n, c_ in zip(el, c_list):
                # 親の頂点に対する処理
                nodes[node_num-1].co_edge(node_n, c_) # 子のエッジの色を持つ
                # 子の頂点に対する処理
                nodes[node_n-1].rm_edge(node_num) # 親のエッジを削除
                s_node(node_n, c_)

    s_node(1,0)


    ans = []
    for ai, bi in zip(a,b):
        if bi in nodes[ai-1].edge:
            ans.append(nodes[ai-1].color[bi])
        else:
            ans.append(nodes[bi-1].color[ai])
        

    print(max(ans))
    [print(c_) for c_ in ans]


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

class Node:
    def __init__(self, num):
        self.num = num
        self.edge = []
        self.color = {}
    
    def ap_edge(self,e):
        self.edge.append(e)

    def rm_edge(self,e):
        self.edge.remove(e)
    
    def co_edge(self,n, c):
        self.color[n] = c




def solve(N: int, a: "List[int]", b: "List[int]"):
    nodes = [Node(num+1) for num in range(N)]

    for ai, bi in zip(a,b):
        nodes[ai-1].ap_edge(bi)
        nodes[bi-1].ap_edge(ai)

    def s_node(node_num, prev_c):
        el = nodes[node_num-1].edge
        # print("node_num:{} el:{}".format(node_num, el))
        if len(el)>0:
            if prev_c not in list(range(1,len(el)+1)):
                c_list = list(range(1,len(el)+1))
            else:
                c_list = list(range(1,len(el)+2))
                c_list.pop(prev_c-1)
            
            if len(c_list) != len(el):
                print("error")
            # print("c_list:{} prev_c:{}".format(c_list, prev_c))

            for node_n, c_ in zip(el, c_list):
                # 親の頂点に対する処理
                nodes[node_num-1].co_edge(node_n, c_) # 子のエッジの色を持つ
                # 子の頂点に対する処理
                nodes[node_n-1].rm_edge(node_num) # 親のエッジを削除
                s_node(node_n, c_)

    s_node(1,0)


    ans = []
    for ai, bi in zip(a,b):
        if bi in nodes[ai-1].edge:
            ans.append(nodes[ai-1].color[bi])
        else:
            ans.append(nodes[bi-1].color[ai])
        

    print(max(ans))
    [print(c_) for c_ in ans]


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

class Node:
    def __init__(self, num):
        self.num = num
        self.edge = []
        self.color = {}
    
    def ap_edge(self,e):
        self.edge.append(e)

    def rm_edge(self,e):
        self.edge.remove(e)
    
    def co_edge(self,n, c):
        self.color[n] = c




def solve(N: int, a: "List[int]", b: "List[int]"):
    nodes = [Node(num+1) for num in range(N)]

    for ai, bi in zip(a,b):
        nodes[ai-1].ap_edge(bi)
        nodes[bi-1].ap_edge(ai)

    def s_node(node_num, prev_c):
        el = nodes[node_num-1].edge
        # print("node_num:{} el:{}".format(node_num, el))
        
        if prev_c not in list(range(1,len(el)+1)):
            c_list = list(range(1,len(el)+1))
        else:
            c_list = list(range(1,len(el)+2))
            c_list.pop(prev_c-1)
        
        if len(c_list) != len(el):
            print("error")
        # print("c_list:{} prev_c:{}".format(c_list, prev_c))

        for node_n, c_ in zip(el, c_list):
            # 親の頂点に対する処理
            nodes[node_num-1].co_edge(node_n, c_) # 子のエッジの色を持つ
            # 子の頂点に対する処理
            nodes[node_n-1].rm_edge(node_num) # 親のエッジを削除
            s_node(node_n, c_)

    s_node(1,0)


    ans = []
    for ai, bi in zip(a,b):
        if bi in nodes[ai-1].edge:
            ans.append(nodes[ai-1].color[bi])
        else:
            ans.append(nodes[bi-1].color[ai])
        

    print(max(ans))
    [print(c_) for c_ in ans]


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
G=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  G[a].append([b,i])

ans=[None]*(N-1)
def dfs(now,color):
  cnt=1
  for to,j in G[now]:
    if cnt==color:
      cnt+=1
    ans[j]=cnt
    dfs(to,cnt)
    cnt+=1
dfs(0,0)
print(max(ans))
print(*ans,sep="\n")

Submission status: Runtime Error

Solution code:
N = int(input())
V = [[] for _ in range(N)]
color = [-1] * (N - 1)

for i in range(N - 1):
    a, b = map(int, input().split())
    V[a - 1].append([b - 1, i])
    V[b - 1].append([a - 1, i])

# 最大接続数 = 色の数
q_connect = 0
for i in V:
    q_connect = max(len(i), q_connect)

def dfs(v, index, pre_color):
    # print(v, index, pre_color)
    if index != -1:
        color[index] = pre_color
    new_color = 0
    for adj, idx in V[v]:
        if color[idx] != -1: continue
        while new_color == pre_color:
            new_color += 1
            if new_color == q_connect:
                new_color = 0
        dfs(adj, idx, new_color)
        new_color += 1

dfs(0, -1, -1)
color = list(map(lambda x: x + 1, color))

print(q_connect)
for a in color:
    print(a)

Submission status: Runtime Error

Solution code:
from queue import deque

N = int(input())

A = []
B = [[]for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    A.append([a, b])
    B[a-1].append(b-1)

X = max(len(i) for i in B)

print(X)

q = deque([0])
color = [[-1]*N]
ans = {}
while q:
    nord = q.popleft()
    c = 0
    for i, v in enumerate(B[nord]):
        if color[v] == i:
            c += 1
        color[i] = c + i 
        ans[(nord, i)] = c + i
        q.append(v)

for i, j in B:
    print(ans[(i-1, j-1)]+1)

Submission status: Runtime Error

Solution code:
n = int(input())
s = [[] for _ in range(n+1)]
c = [0]*(n+1)
for i in range(n-1):
    a,b = map(int, input().split())
    s[a].append((b,i+1))
    s[b].append((a,i+1))
#print(s)

stack = [(1,1)]   #(now,color)
c[1] = 1
while stack:
    v,w = stack.pop()
    #print(v,w)
    a = s[v]
    for i in range(len(a)):
        if (c[a[i]]!=0):
            continue
        else:
            if (w==2):
                color = 1
                c[a[i]] = 1
            elif (w==1):
                color = 2
                c[a[i]]=2
        stack.append((a[i],color))
        #print(stack)
#print(c)
del c[0]
print(*c, sep="\n")

Submission status: Runtime Error

Solution code:
import sys


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


sys.setrecursionlimit(10 ** 9)

MOD = 10 ** 9 + 7


def main():
    N = int(input())
    A = [0 for _ in range(N)]
    C = []

    for _ in range(N - 1):
        a, b = map(int, input().split())
        A[a - 1] += 1
        A[b - 1] += 1
        C.append([a, b])
    S = max(A)
    print(S)
    B = [0 for _ in range(N - 1)]
    check = [[0] for _ in range(N)]
    for i in range(N - 1):
        c = C[i]
        a = c[0]
        b = c[1]
        if len(check[a - 1]) > 1 or len(check[b - 1]) > 1:
            if (1 in check[a - 1]) or (1 in check[b - 1]):
                t = []
                for s in range(S):
                    if (s + 1) not in check[a - 1]:
                        if (s + 1) not in check[b - 1]:
                            t.append(s + 1)
                B[i] = max(t)
            else:
                B[i] = 1
            check[a - 1].append(B[i])
            check[b - 1].append(B[i])
        else:
            B[i] = 1
            check[a - 1].append(1)
            check[b - 1].append(1)

    print(*B, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

AtCoder Beginner Contest 146
 日本語 
 sawakee (Guest) 
コンテスト時間: 2019-11-24(日) 21:00 ~ 2019-11-24(日) 22:40 (100分)AtCoderホームへ戻る
 トップ
 問題
 質問
 提出
 提出結果
 順位表
 バーチャル順位表
 コードテスト
 解説
D - Coloring Edges on Tree / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
400
 点

問題文
N
 頂点の木 
G
 が与えられます。 頂点には 
1
 から 
N
 までの番号がついており、
i
 本目の辺は頂点 
a
i
 と頂点 
b
i
 を結んでいます。

G
 の辺を何色かで塗り分けることを考えます。 このとき、各頂点について、その頂点を端点に持つ辺の色がすべて相異なるようにしたいです。

上記の条件を満たす塗り分けの中で、使用する色の数が最小であるようなものを 
1
 つ構築してください。

制約
2
≤
N
≤
10
5
1
≤
a
i
<
b
i
≤
N
入力はすべて整数
与えられるグラフは木である
入力
入力は以下の形式で標準入力から与えられる。

N

a
1
 
b
1

a
2
 
b
2

⋮

a
N
−
1
 
b
N
−
1

出力
出力は 
N
 行からなる。

1
 行目に使用する色の数 
K
 を出力せよ。

i
+
1
 行目 
(
1
≤
i
≤
N
−
1
)
 に 
i
 番目の辺の色を表す整数 
c
i
 を出力せよ。ここで 
1
≤
c
i
≤
K
 でなければならない。

問題文中の条件を満たし、使用する色の数が最小であるような塗り分けが複数存在するときは、そのうちのどれを出力しても構わない。

入力例 1 
Copy
3
1 2
2 3
出力例 1 
Copy
2
1
2
入力例 2 
Copy
8
1 2
2 3
2 4
2 5
4 7
5 6
6 8
出力例 2 
Copy
4
1
2
3
4
1
1
2
入力例 3 
Copy
6
1 2
1 3
1 4
1 5
1 6
出力例 3 
Copy
5
1
2
3
4
5
言語
ソースコード
1
​
※ 512 KiB まで
※ ソースコードは「Main.拡張子」で保存されます




FacebookTwitterHatena共有
ルール 用語集
利用規約 プライバシーポリシー 個人情報保護方針 企業情報 よくある質問 お問い合わせ 資料請求
Copyright Since 2012 ©AtCoder Inc. All rights reserved.
 ページトップ

Submission status: Runtime Error

Solution code:
N=int(input())
AB=[list(map(int,input().split())) for _ in range(N-1)]

G=[[] for _ in range(N)]
cnt=[0]*N
for i in range(N-1):
  cnt[AB[i][0]-1]+=1
  cnt[AB[i][1]-1]+=1
  G[AB[i][0]-1].append(AB[i][1])
  G[AB[i][1]-1].append(AB[i][0])
K=max(cnt)
print(K)
#print(G)
#print(cnt)

color=[[] for _ in range(N)]
for i in range(N-1):
  colors=[n for n in range(1,K+1)]
  for j in range(len(color[AB[i][0]-1])):
    colors.remove(color[AB[i][0]-1][j])
  for k in range(len(color[AB[i][1]-1])):
    colors.remove(color[AB[i][1]-1][k])
  color[AB[i][0]-1].append(colors[0])
  color[AB[i][1]-1].append(colors[0])
  print(colors[0])

Submission status: Runtime Error

Solution code:
n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  g[a-1].append([b-1,i])
  g[b-1].append([a-1,i])
print(max(len(v) for v in g))
l=[0]*(n-1)
def dfs(v,p=-1,c=-1):
  k=1
  for u,e in g[v]:
    if u==p: continue
    if k==c: k+=1
    l[e]=k
    dfs(u,v,k)
    k+=1
dfs(0)
for c in l: print(c)

Submission status: Runtime Error

Solution code:
n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  g[a-1].append([b-1,i])
  g[b-1].append([a-1,i])
l=[0]*(n-1)
def dfs(v,p=-1,c=-1):
  k=1
  for u,e in g[v]:
    if u==p: continue
    if k==c: k+=1
    l[e]=k
    k+=1
    dfs(u,v,l[e])
dfs(0)
print(max(len(v) for v in g))
print('\n'.join(map(str,l)))

Submission status: Runtime Error

Solution code:
n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  g[a-1].append([b-1,i])
  g[b-1].append([a-1,i])
l=[0]*(n-1)
def dfs(v,p=-1,c=-1):
  k=1
  for u,e in g[v]:
    if u==p: continue
    if k==c: k+=1
    l[e]=k
    k+=1
    dfs(u,v,l[e])
dfs(0)
print(max(len(g[v]) for v in range(n)))
for c in l: print(c)

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,sys.stdin.readline().split())
  g[a-1].append([b-1,i])
  g[b-1].append([a-1,i])
l=[0]*(n-1)
def dfs(v,p=-1,c=-1):
  k=1
  for u,e in g[v]:
    if u==p: continue
    if k==c: k+=1
    l[e]=k
    k+=1
    dfs(u,v,l[e])
dfs(0)
print(max(len(g[v]) for v in range(n)))
for c in l: print(c)

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
l=[0]*n
e=[]*(n-1)
g=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,sys.stdin.readline().split())
  e.append([a-1,b-1])
  l[a-1]+=1
  l[b-1]+=1
k=max(l)
print(k)
c=[set(range(1,k+1)) for _ in range(n)]
for a,b in e:
  m=min(c[a]&c[b])
  c[a].remove(m)
  c[b].remove(m)
  print(m)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque
n=int(input())
edge=np.array(list(list(map(int,input().split())) for _ in range(n-1)))
color=np.zeros(n-1)
d=deque()


s=1
d.append(s)
while d:
  c=1
  s=d.popleft()
  check=[]
  seen=[]
  for i in range(n-1):
    if s in edge[i]:
      e=edge[i][edge[i]!=s]
      if color[i]==0:
        d.append(e[0])
        check.append(i)
      else:
        seen.append(color[i])
  for j in check:
    if c not in seen:
      color[j]=c
      c+=1
    else:
      while c in seen:
        c+=1
      color[j]=c
      c+=1
print(int(max(color)))
print(" ".join(list(map(lambda x: str(int(x)), color))))

Submission status: Runtime Error

Solution code:
N = int(input())
g = [[] for _ in range(N)]
ans = [0 for _ in range(N-1)]

def dfs(v, c=-1, p=-1):
    k = 1
    for i in range(len(g[v])):
        u = g[v][i][0]
        ei = g[v][i][1]
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)


for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, i))
    g[b].append((a, i))
dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
N = int(input())
g = [[] for _ in range(N)]
ans = [[] for _ in range(N-1)]

def dfs(v, c=-1, p=-1):
    k = 1
    for i in range(len(g[v])):
        u = g[v][i][0]
        ei = g[v][i][1]
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)


for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, i))
    g[b].append((a, i))
dfs(0)
mx = 0

Submission status: Runtime Error

Solution code:
N = int(input())
g = [[] for _ in range(N)]
ans = [[] for _ in range(N-1)]

def dfs(v, c=-1, p=-1):
    k = 1
    for i in range(len(g[v])):
        u = g[v][i][0]
        ei = g[v][i][1]
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)


for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, i))
    g[b].append((a, i))
dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
# D - Coloring Edges on Tree

n = int(input())
A = []
B = []

# 2次元配列で辺（頂点,遷移先の頂点）を管理する
D = [[] for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    D[a].append(b)
    D[b].append(a)
    A.append(a)
    B.append(b)

print(max([len(d) for d in D]))

C = {}

def dfs(node, par, col):
    cid = 1
    for chi in D[node]:
        if chi==par:
            continue
        else:
            if cid==col:
                cid += 1
            C[(node, chi)] = cid
            C[(chi, node)] = cid
            dfs(chi, node, cid)
            cid += 1

dfs(0,0,0)

for a, b in zip(A, B):
    print(C[(a,b)])

Submission status: Runtime Error

Solution code:
# D - Coloring Edges on Tree

n = int(input())
A = []
B = []

# 2次元配列で辺（頂点,遷移先の頂点）を管理する
D = [[] for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    D[a].append(b)
    D[b].append(a)
    A.append(a)
    B.append(b)

print(max([len(d) for d in D]))

C = {}

def dfs(node, par, col):
    cid = 1
    for chi in D[node]:
        if chi==par:
            continue
        else:
            if cid==col:
                cid += 1
            C[(node, chi)] = cid
            dfs(chi, node, cid)
            cid += 1

dfs(0,0,0)

for a, b in zip(A, B):
    print(C[(a,b)])

Submission status: Runtime Error

Solution code:
def dfs(G,v,p,color):
    cnt=1
    for nv in G[v]:
        if(nv==p):
            continue
        if cnt in liset[v]:
            while(cnt in liset[v]):
                cnt+=1
        liset[v].add(cnt)
        liset[nv].add(cnt)
        dic[str(v)+'t'+str(nv)]=cnt
        dfs(G,nv,v,cnt)
N=int(input())
G=[[] for i in range(N)]
e=[]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
    e.append([a,b])
l=0
for i in range(N):
    l=max(l,len(G[i]))
liset=[set() for i in range(N)]
dic={}
dfs(G,0,-1,0)
print(l)
for i in range(N-1):
    if str(e[i][0])+'t'+str(e[i][1]) in dic:
        print(dic[str(e[i][0])+'t'+str(e[i][1])])
    else:
        print(dic[str(e[i][1])+'t'+str(e[i][0])])

Submission status: Runtime Error

Solution code:
def dfs(G,v,p,color):
    cnt=1
    for nv in G[v]:
        if(nv==p):
            continue
        if cnt in liset[v]:
            while(cnt in liset[v]):
                cnt+=1
        liset[v].add(cnt)
        liset[nv].add(cnt)
        dfs(G,nv,v,cnt)
N=int(input())
G=[[] for i in range(N)]
e=[]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
    e.append([a,b])
l=0
for i in range(N):
    l=max(l,len(G[i]))
liset=[set() for i in range(N)]
dfs(G,0,-1,0)
print(l)
for i in range(N-1):
    print(list(liset[e[i][0]]&liset[e[i][1]])[-1])

Submission status: Runtime Error

Solution code:
def dfs(G,v,p,color):
    cnt=1
    for nv in G[v]:
        if(nv==p):
            continue
        if cnt in liset[v]:
            while(cnt in liset[v]):
                cnt+=1
        liset[v].add(cnt)
        liset[nv].add(cnt)
        dfs(G,nv,v,cnt)
N=int(input())
G=[[] for i in range(N)]
e=[]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
    e.append([a,b])
l=0
for i in range(N):
    l=max(l,len(G[i]))
liset=[set() for i in range(N)]
dfs(G,0,-1,0)
for i in range(N-1):
    print(list(liset[e[i][0]]&liset[e[i][1]])[-1])