{"problem":{"name":"[ICPC 2021 Macao R] Colorful Tree","description":{"content":"Your task is to maintain a colorful tree and process queries. At the beginning, there is only one vertex numbered $1$ with color $C$ on the tree. Then there are $q$ operations of two types coming in ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":6000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9665"},"statements":[{"statement_type":"Markdown","content":"Your task is to maintain a colorful tree and process queries.\n\nAt the beginning, there is only one vertex numbered $1$ with color $C$ on the tree. Then there are $q$ operations of two types coming in order:\n- $0$ $x$ $c$ $d$: Add a new vertex indexed $(n+1)$ with color $c$ to the tree, where $n$ is the current number of existing vertices. An edge connecting vertex $x$ and $(n+1)$ with length $d$ will also be added to the tree.\n- $1$ $x$ $c$: Change the color of vertex $x$ to $c$.\n\nAfter each operation, you should find a pair of vertices $u$ and $v$ ($1 \\le u, v \\le n$) with $\\textbf{different}$ colors in the current tree so that the distance between $u$ and $v$ is as large as possible.\n\nThe distance between two vertices $u$ and $v$ is the length of the shortest path from $u$ to $v$ on the tree.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line of the input contains two integers $q$ and $C$ ($1 \\le q \\le 5 \\times 10^5$, $1 \\le C \\le q$) indicating the number of operations and the initial color of vertex $1$.\n\nFor the following $q$ lines, each line describes an operation taking place in order with $3$ or $4$ integers.\n- If the $i$-th line contains $4$ integers $0$, $x_i$, $c_i$ and $d_i$ ($1 \\le x_i \\le n$, $1 \\le c_i \\le q$, $1 \\le d \\le 10^9$), the $i$-th operation will add a new vertex $(n + 1)$ with color $c_i$ to the tree and connect it to vertex $x_i$ with an edge of length $d_i$.\n- If the $i$-th line contains $3$ integers $1$, $x_i$ and $c_i$ ($1 \\le x_i \\le n$, $1 \\le c_i \\le q$), the $i$-th operation will change the color of vertex $x_i$ to $c_i$.\n\nIt's guaranteed that the sum of $q$ of all test cases will not exceed $5 \\times 10^5$.\n\n## Output\n\nFor each operation output the maximum distance between two vertices with different colors. If no valid pair exists output $0$ instead.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9665","tags":["线段树","2021","O2优化","树论","ICPC","澳门"],"sample_group":[["2\n1 1\n0 1 1 1\n5 1\n0 1 1 1\n0 1 2 1\n0 3 3 1\n1 4 1\n1 3 1","0\n0\n2\n3\n2\n0"]],"created_at":"2026-03-03 11:09:25"}}