Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

We have a tree with N vertices numbered 1 to N. The i-th edge in the tree connects…

  1. User

    We have a tree with N vertices numbered 1 to N. The i-th edge in the tree connects Vertex u_i and Vertex v_i, and its length is w_i. Your objective is to paint each vertex in the tree white or black (it is fine to paint all vertices the same color) so that the following condition is satisfied:

    • For any two vertices painted in the same color, the distance between them is an even number.

    Find a coloring of the vertices that satisfies the condition and print it. It can be proved that at least one such coloring exists under the constraints of this problem.

    Constraints

    • All values in input are integers.
    • 1 \leq N \leq 10^5
    • 1 \leq u_i < v_i \leq N
    • 1 \leq w_i \leq 10^9

    Input

    Input is given from Standard Input in the following format:

    N u_1 v_1 w_1 u_2 v_2 w_2 . . . u_{N - 1} v_{N - 1} w_{N - 1}

    Output

    Print a coloring of the vertices that satisfies the condition, in N lines. The i-th line should contain 0 if Vertex i is painted white and 1 if it is painted black.

    If there are multiple colorings that satisfy the condition, any of them will be accepted.

    Examples

    Input

    3 1 2 2 2 3 1

    Output

    0 0 1

    Input

    5 2 5 2 2 3 10 1 3 8 3 4 2

    Output

    1 0 1 0 1

  2. DeepSeek Assistant

    We need to produce a coloring of vertices into two colors (0/1) such that for any two vertices of the same color, the distance between them is even. Equivalent to: For any two vertices, if distance is odd, they must be of opposite colors. If distance is even, they must be same color? Actually condition: "For any two vertices painted in the same color, the distance between them is an even number." That means: If two vertices have same color -> distance even. Contrapositive: If distance odd -> they must have different colors. However, it does NOT require that if distance even they must be same color. So it's a weaker condition: we can assign colors arbitrarily as long as odd distances force different colors. This is essentially a bipartite condition on a graph where vertices are connected if distance is odd? But we have a tree, distances are defined.

    We need to assign colors 0/1 to vertices such that for any pair (i,j) with dist(i,j) odd, we have col[i] != col[j]. For even dist, they can be same or different. This is exactly a graph coloring of the "odd-distance graph" which is essentially the parity of path lengths mod 2.

    In a tree, the parity of distance between two vertices is determined by the parity of the sum of edge lengths along the path. Edge lengths can be odd or even. So distance parity is not just based on number of edges but also edge lengths.

    We need to assign colors to vertices such that if the parity of distance is odd -> different colors.

    That is reminiscent of labeling vertices with 0/1 such that for any edge (u,v,w), we require col[u] XOR col[v] = w mod 2? Because distance parity along an edge is w mod 2. For a path, distance parity = sum of edge parities mod 2. For consistency, if we set col[u] XOR col[v] = parity of distance between u and v mod 2, then condition would be that for any two vertices, col[u] XOR col[v] = dist(u,v) mod 2. Then if dist mod 2 = 0, col equal; if 1, col differ. That satisfies the condition exactly: same color implies even distance. So if we can assign bits to vertices such that for all pairs, col[u] XOR col[v] = dist(u,v) mod 2, then it's perfect. But is it possible? That would require that the function dist mod 2 behaves like an XOR difference derived from a vertex labeling. In any tree, we can pick an arbitrary root and assign each vertex a parity value equal to the parity of distance from root. Then for any two vertices u and v, dist(u,v) mod 2 = (dist(root,u) + dist(root,v) - 2dist(root,lca)) mod 2 = (dist(root,u) + dist(root,v)) mod 2 because 2dist(root,lca) is even. So dist(u,v) mod 2 = (dist(root,u) mod 2) XOR (dist(root,v) mod 2) (since sum mod 2 = XOR). So if we set col[u] = dist(root,u) mod 2, then col[u] XOR col[v] = dist(u,v) mod 2. That works! But wait, careful: For any two vertices, dist(u,v) = dist(root,u)+dist(root,v)-2dist(root,lca). The term 2dist(root,lca) is even, so modulo 2 it's 0. Hence dist(u,v) mod 2 = (dist(root,u) mod 2) XOR (dist(root,v) mod 2). Yes. So labeling vertices by parity of distance from root yields exactly the property: col[u] XOR col[v] = parity of distance. Then same color => parity 0 => even distance. So condition satisfied.

    Thus solution: choose arbitrary root (say vertex 1), compute for each vertex the parity (even/odd) of the sum of edge lengths from root to that vertex (mod 2). Then output 0 for parity 0 (even), 1 for parity 1 (odd) (or any mapping). That yields a valid coloring.

    But is it always valid? Edge lengths w_i up to 1e9, but we only need parity. So we can compute distances mod 2 using BFS/DFS. Complexity O(N). This is essentially a bipartite coloring based on parity of weighted distances.

    Wait: Does this guarantee that any two vertices with same parity have even distance? Yes, because if both have same parity, XOR = 0 => dist mod2 =0 => even. So condition satisfied.

    Thus output is straightforward.

    But careful: In example 1:

    Tree: edges: 1-2 w=2 (even), 2-3 w=1 (odd). Root 1: dist(1)=0 (even) => col 0. dist(2)=2 (even) => col 0. dist(3)=2+1=3 (odd) => col 1. That matches example output: 0,0,1. Good.

    Example 2: Let's test. Input: 5 2 5 2 2 3 10 1 3 8 3 4 2 Edges: (2,5,2), (2,3,10), (1,3,8), (3,4,2). Compute root 1: dist1=0 even => col 0? But example output: first line 1? Actually example output: 1,0,1,0,1. So root 1 colored 1 in example. So they used a different root or mapping. That's fine, any coloring works.

    Let's check if our method yields consistent coloring with condition? root1=0 even => col[1]=0; dist to 3: edge (1,3) w=8 even => dist=8 even => col[3]=0; dist to 2: from 1 to 2 path: 1-3 (8) + 3-2 (10) = 18 even => col[2]=0; dist to 4: 1-3 (8) + 3-4 (2) =10 even => col[4]=0; dist to 5: 1-3 (8) + 3-2 (10) + 2-5 (2) =20 even => col[5]=0. That yields all 0. But is that valid? Check condition: For any two vertices, same color => even distance? All same color, so we need every distance to be even. But distance between 3 and 2 is 10 (even) ok; 1 and 2 is 18 even; 2 and 5 is 2 even; but distance between 4 and 5? Path: 4-3 (2) + 3-2 (10) + 2-5 (2) = 14 even; etc. Wait is there any odd distance? Let's compute all distances: all sums of even numbers: all edges? Let's list edge parities: (2,5,2) even, (2,3,10) even, (1,3,8) even, (3,4,2) even. All edges even. So the whole tree has all edge lengths even. Then any distance is even (sum of evens). So condition holds trivially: all vertices can be same color. So both all-0 and the given example (1,0,1,0,1) are valid. So our method works.

    Thus answer: compute parity of distances from root using DFS/BFS (mod 2). Output parity as 0/1.

    Edge case: negative? No.

    Implementation: adjacency list storing (neighbor, weight). Use recursion or stack. N up to 1e5, recursion depth might be large; use iterative DFS or set recursion limit.

    We'll do DFS from node 1. Use array parity[N+1] initialized to -1. Set parity[1]=0. For each neighbor, parity[neighbor] = parity[current] XOR (w%2). Because distance parity to neighbor = current parity XOR (w mod 2). Because adding w mod 2 toggles parity.

    Then output parity[i] for i=1..N.

    That's it.

    But let's double-check: The property that dist(u,v) mod 2 = parity[u] XOR parity[v] holds if parity is based on root distance mod2. Because parity[u] = dist(root,u) mod2. Then dist(u,v) mod2 = (dist(root,u) + dist(root,v) - 2dist(root,lca)) mod2 = parity[u] XOR parity[v]. Since -2dist(...) mod2=0. Yes.

    Thus condition satisfied.

    We need to be sure that the condition does not require distance even for same color if they are same color but distance odd? That would violate condition. Our assignment ensures same color => parity same => XOR=0 => distance even. So fine.

    Thus solution trivial.

    But note: the problem statement: "Your objective is to paint each vertex in the tree white or black (it is fine to paint all vertices the same color) so that the following condition is satisfied: * For any two vertices painted in the same color, the distance between them is an even number." That's exactly what we solved.

    Thus output.

    But wait, could there be a scenario where our assignment yields that two vertices of opposite color have distance even? That's allowed because condition only restricts same-color pairs. So fine.

    Thus code.

    Edge Cases: N=1. Then only one vertex, condition vacuously true. Our DFS yields parity[1]=0 => output 0.

    Time O(N). Memory O(N).

    Now produce final answer. Use Python.

    Implementation:

    def solve(): import sys sys.setrecursionlimit(200000) input = sys.stdin.readline N = int(input()) adj = [[] for _ in range(N+1)] for _ in range(N-1): u,v,w = map(int,input().split()) adj[u].append((v,w)) adj[v].append((u,w)) parity = [-1]*(N+1) parity[1]=0 stack = [1] while stack: u = stack.pop() for v,w in adj[u]: if parity[v]==-1: parity[v] = parity[u] ^ (w&1) # w%2 stack.append(v) out = '\n'.join(str(parity[i]) for i in range(1,N+1)) print(out)

    That's it.

    But need to be careful: recursion? iterative stack fine.

    Check if all vertices visited: tree is connected, so yes.

    Thus final answer.

    Now let's produce the explanation and code in the final response. ```python import sys

    def solve() -> None: sys.setrecursionlimit(200000) input = sys.stdin.readline

    N = int(input())
    adj = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        adj[u].append((v, w))
        adj[v].append((u, w))
    
    parity = [-1] * (N + 1)   # 0 for even, 1 for odd
    parity[1] = 0
    stack = [1]
    while stack:
        u = stack.pop()
        for v, w in adj[u]:
            if parity[v] == -1:
                parity[v] = parity[u] ^ (w & 1)   # w % 2
                stack.append(v)
    
    out = "\n".join(str(parity[i]) for i in range(1, N + 1))
    print(out)
    

    if name == "main": solve()