In the Land of Fire there are n villages and n-1 bidirectional road, and there is a path…
- User
In the Land of Fire there are n villages and n-1 bidirectional road, and there is a path between any pair of villages by roads. There are only two types of roads: stone ones and sand ones. Since the Land of Fire is constantly renovating, every morning workers choose a single road and flip its type (so it becomes a stone road if it was a sand road and vice versa). Also everyone here loves ramen, that's why every morning a ramen pavilion is set in the middle of every stone road, and at the end of each day all the pavilions are removed.
For each of the following m days, after another road is flipped, Naruto and Jiraiya choose a simple path — that is, a route which starts in a village and ends in a (possibly, the same) village, and doesn't contain any road twice. Since Naruto and Jiraiya also love ramen very much, they buy a single cup of ramen on each stone road and one of them eats it. Since they don't want to offend each other, they only choose routes where they can eat equal number of ramen cups. Since they both like traveling, they choose any longest possible path. After every renovation find the maximal possible length of a path (that is, the number of roads in it) they can follow. Input
The first line contains the only positive integer n (2 ≤ n ≤ 500 000) standing for the number of villages in the Land of Fire.
Each of the following (n-1) lines contains a description of another road, represented as three positive integers u, v and t (1 ≤ u, v ≤ n, t ∈ {0,1}). The first two numbers denote the villages connected by the road, and the third denotes the initial type of the road: 0 for the sand one and 1 for the stone one. Roads are numbered from 1 to (n-1) in the order from the input.
The following line contains a positive integer m (1 ≤ m ≤ 500 000) standing for the number of days Naruto and Jiraiya travel for.
Each of the following m lines contains the single integer id (1 ≤ id ≤ n-1) standing for the index of the road whose type is flipped on the morning of corresponding day.
It is guaranteed that there is a road path between any pair of villages.
Output
Output m lines. In the i-th of them print the only integer denoting the maximal possible length of any valid path on the i-th day.
Example
Input
5 1 2 0 1 3 0 3 5 0 3 4 0 5 3 4 1 3 4
Output
3 2 3 3 2
Note
After the renovation of the 3-rd road the longest path consists of the roads 1, 2 and 4.
After the renovation of the 4-th road one of the longest paths consists of the roads 1 and 2.
After the renovation of the 1-st road one of the longest paths consists of the roads 1, 2 and 3.
After the renovation of the 3-rd road the longest path consists of the roads 1, 2 and 4.
After the renovation of the 4-rd road one of the longest paths consists of the roads 2 and 4.
Assistant
We need to solve this problem: given a tree with n up to 500k, each edge has a type 0/1. Each day we flip one edge's type (given by index). After the flip, we need to find the maximal possible length (number of edges) of a simple path (in the tree) such that along the path, the number of edges of type 1 (stone) is equal to the number of edges of type 0 (sand) i.e., equal number of ramen cups? Actually they buy a single cup on each stone road and one of them eats it; they want to eat equal number of ramen cups, so they want the number of stone edges on the path to be equal for both? Wait: "they buy a single cup of ramen on each stone road and one of them eats it. Since they don't want to offend each other, they only choose routes where they can eat equal number of ramen cups." So they together traverse a path, each stone edge yields a cup which is eaten by either Naruto or Jiraiya. They want to split the cups equally, so total number of stone edges on the path must be even? Actually equal number of cups eaten by each means total stone edges must be even, and they can assign each cup to one of them arbitrarily? The problem statement: "they buy a single cup of ramen on each stone road and one of them eats it. Since they don't want to offend each other, they only choose routes where they can eat equal number of ramen cups." This implies that along the chosen path, there must exist a way to assign each stone edge's cup to either Naruto or Jiraiya such that they end up with equal numbers. Since they can decide who eats each cup, the condition is simply that the total number of stone edges on the path is even. Because they can split them equally as long as total is even. Indeed, if total stone count is k, they can assign floor(k/2) to each only if k even. If k odd, they cannot have equal numbers because each cup is eaten by exactly one person. So the condition is: the path must have an even number of stone edges. Then, they also want the longest such path (max number of edges). They can choose any path (not necessarily simple? They say simple path: doesn't contain any road twice. So it's a simple path in the tree). So problem: After each update (edge flip type), find the maximum length (number of edges) of a simple path in the tree that contains an even number of edges of type 1.
Important: The length is measured in number of edges. So we want max number of edges in a path with even number of type 1.
We have dynamic updates on edge types. Need to answer after each update. n, m up to 500k, so need O((n+m) log n) or similar.
This is reminiscent of dynamic tree problems: maintain diameter under some constraints. For a tree, the longest path satisfying a parity condition on sum of edge weights (mod 2). Actually each edge has weight 0 or 1, we want sum mod 2 = 0. That's essentially a parity constraint on the path's XOR sum? If we assign each edge a value (type), then for a path between u and v, the total number of stone edges is sum of values along the path. This sum mod 2 = parity of the path from u to v. For tree, we can define a root, assign each node a parity value: xor (or sum mod 2) from root to node. Then the sum along path u-v is parity(u) XOR parity(v) (if using XOR) or (parity(u) + parity(v)) mod 2? Actually if we define parity[node] = sum of edge values from root to node mod 2. Then for any path u-v, sum of edge values mod 2 = (parity[u] XOR parity[v]) because the root to u and root to v share the common part up to LCA, which cancels mod 2. So condition that total sum is even (mod 2 = 0) is equivalent to parity[u] = parity[v]. So we need a path between two nodes with same parity (root parity) and we want maximize length (#edges). This is key: The parity constraint becomes: find two nodes with same parity such that distance (in terms of number of edges) between them is maximum. Distance is measured as number of edges, not weighted by type. So we need the maximum distance between two nodes of same parity.
Because the tree is unweighted (each edge length = 1), but we have parity labels on nodes. After each update (flip edge type), the parity of all nodes in one component of that edge? Actually flipping an edge type toggles the parity of all nodes on one side of that edge. Because if we cut the edge, we have two subtrees. Flipping the type of that edge changes the parity of all nodes on one side relative to root if we keep root fixed. So we need to support updates that toggle the parity of all nodes in a subtree (if root is fixed appropriately). Specifically, if we root the tree arbitrarily (say at node 1). For an edge (u, v) where parent relationship: let parent be p, child be c. Then flipping the type of edge (p, c) toggles the parity of node c and all nodes in the subtree of c. Because the parity is defined as XOR from root. Changing the edge value toggles whether the parity of c is flipped relative to p. That effectively toggles parity of all nodes in c's subtree. So the update is: given an edge, toggle parity of all nodes in the subtree of the child side (depending on rooting). So we need a data structure that supports subtree XOR (or toggle) updates on a binary node label (parity), and we need to maintain the maximum distance between two nodes having the same parity (or also opposite? only same). After each update, we need to query the maximum distance among pairs of nodes with parity 0, and similarly parity 1, and take max of those two? Actually we need maximum distance between any two nodes with same parity. So effectively we have two colors (0 and 1) assigned to nodes, and each update toggles colors of a whole subtree. And we need to maintain the diameter of each color class, then answer = max(diameter of color0, diameter of color1). Because the longest path with even number of stones = longest path between two nodes of same parity.
Now this becomes a dynamic tree problem: We have a tree, initially nodes have colors (parity 0/1). We need to support subtree color flip updates, and after each update, report the maximum distance between two nodes of same color. Distances are tree distances (number of edges). n up to 500k, m up to 500k.
We need to handle many updates quickly. Subtree updates are range updates on the Euler tour (DFS order). We can represent the tree as an array of nodes in Euler tour (preorder). A subtree corresponds to a contiguous segment in the Euler tour if we use entry and exit times. Then flipping colors of a subtree is range XOR on the array of colors (0/1). So we can maintain colors with a segment tree supporting lazy range XOR. But we also need to compute diameters of each color class dynamically under updates. This is more complex.
We need to compute for each color, the maximum distance between two nodes of that color. In static scenario, we could compute for each color the two farthest nodes (diameter) by two BFS from any node of that color, but that's O(n) per query, too slow.
We need a data structure that can maintain the diameter of a set of nodes that changes dynamically (colors toggled). Subtree toggle means many nodes may change color. We need to maintain for each color the diameter of its node set. After each update, we need to answer the max of the two diameters.
This is reminiscent of problems like "dynamic tree diameter with node activation" but here activation is color, and we have two sets, but nodes can move from one set to another. We can think of it as each node belongs to one of two groups, and we flip groups for a whole subtree.
Potential approaches:
- Use heavy-light decomposition and segment trees that maintain diameter of a set of nodes within a segment, and combine using tree distances. However, the diameter of a set of nodes in a tree can be maintained by storing the two farthest nodes within the set, and the distance between them can be computed using LCA. But dynamic updates over a range require merging information from segments. Since the set of nodes is defined by colors, we need to maintain for each segment of Euler tour, for each color, the diameter of nodes with that color within that segment. Then we can combine across segments using segment tree with lazy color flip that swaps the color information for that segment. That is promising.
Specifically, we can build a segment tree over the Euler tour array (size n). In each node of segment tree, we store for both colors (0 and 1) the pair of nodes (or distances?) that represent the "diameter" of the nodes of that color within that segment. But careful: The diameter of a set of nodes in a tree is not a property that can be easily combined from two disjoint sets if we only know the diameters of each set. However, we can combine: if we have two sets A and B (disjoint, but their nodes are anywhere in the tree), the diameter of A ∪ B is the maximum among: diameter(A), diameter(B), and the maximum distance between any node in A and any node in B. The maximum distance between a node in A and a node in B can be found if we know for each set the farthest node from some reference? Actually we need to be able to compute the maximum distance between any node in A and any node in B. This can be done if for each set we store the two farthest nodes? But we can also store something like the pair of nodes that are farthest apart within the set. However, to combine two sets, we might need more information: For each set, we need to know the "extreme" nodes: the node that is farthest from a given point? Actually the maximum distance between A and B equals max_{a in A, b in B} dist(a,b). This can be computed as: max( diam(A), diam(B), max_{a in A, b in B} dist(a,b) )? Actually the diameter of union is max(diam(A), diam(B), max_{a in A, b in B} dist(a,b)). So we need to compute the max cross distance.
If we have for each set S: we can store the pair of nodes that realize the diameter, but that alone might not be enough to compute max cross distance. However, we can also store for each set S the "best" node that gives max distance to the other set? Actually to compute max_{a in A, b in B} dist(a,b), we can consider that dist(a,b) = depth[a] + depth[b] - 2*depth[lca(a,b)]. Since we are on a tree, we can use the trick of converting distance to depth and LCA. For a static tree, we can precompute LCA in O(1) with RMQ. So if we have two sets of nodes, we can compute the maximum distance between them by considering the deepest node? Not exactly: The maximum distance between two nodes from different sets might be between the deepest node of one set and the shallowest? Actually depth alone not enough due to LCA. But there is known technique: For any set of nodes, you can compute the pair of nodes that are farthest apart (diameter) and also you can compute the node that is farthest from a given node. For combining two sets, if we have the diameters, we can compute cross distance by considering the four endpoints of the diameters? Is it true that max cross distance is one of distances between endpoints of the diameters? Not necessarily: Example: A's diameter endpoints (a1,a2), B's (b1,b2). It could be that the farthest a in A and b in B are not these endpoints. But I think for tree distances, the maximum distance between two sets can be found by considering the distances between the four endpoints: a1, a2, b1, b2. I recall that for two sets in a tree, the farthest pair between the sets is achieved by endpoints of the diameters of the sets. This is a property: For any two sets of nodes in a tree, the maximum distance between a node in A and a node in B equals max( dist(u_A, u_B) ) where u_A is an endpoint of the diameter of A and u_B is an endpoint of the diameter of B? Let's test: Suppose A = {x,y} with diam xy, B = {z,w} with diam zw. Could there be a pair (a,b) with a in A, b in B such that dist(a,b) > max(dist(x,z), dist(x,w), dist(y,z), dist(y,w))? Consider tree: four nodes: a1, a2, b1, b2 arranged like a line: a1 - a2 - b1 - b2. A = {a1, a2}, diameter endpoints a1 and a2, dist=1. B = {b1, b2}, diameter endpoints b1 and b2, dist=1. Cross distances: dist(a1,b1)=2, dist(a1,b2)=3, dist(a2,b1)=1, dist(a2,b2)=2. Max cross =3 (a1,b2). That is indeed one of the pairs between endpoints: a1 (diameter endpoint of A) and b2 (diameter endpoint of B). Another example: A = {a1, a2, a3}? But if A's diameter endpoints are a1,a2, B's are b1,b2. Could there be a node a3 in A not an endpoint that gives larger distance to some b? Suppose the tree is a star: center c, leaves a1,a2,b1,b2. A = {a1, a2}, diam endpoints a1,a2 distance 2 via c? Actually dist(a1,a2)=2. B = {b1,b2}, diam endpoints b1,b2 distance 2. Cross distances: dist(a1,b1)=2, dist(a1,b2)=2, dist(a2,b1)=2, dist(a2,b2)=2. All same. So fine.
Consider a more complex tree: A has nodes {x,y,z} where diam endpoints are x and y. B has nodes {u,v,w} where diam endpoints are u and v. Could there be a pair (z, w) with larger distance? Let's think about tree metrics: For any three nodes a, b, c, the function f(p)=dist(p, x) is convex? Actually, the set of nodes that are farthest from a given node is an endpoint of the diameter of the whole tree. But for subsets, I think the property holds: For any sets A and B in a tree, the maximum distance between a node in A and a node in B is achieved by two nodes that are each an endpoint of the diameter of their respective sets. I recall a known result: If you have two connected subgraphs or two sets of nodes, the farthest pair between them is comprised of endpoints of their diameters. This is used in data structures for dynamic diameter of forests (like segment tree on Euler tour storing farthest pair). Let's verify.
Let D_A be the diameter of A: nodes a and a' such that dist(a,a') = diam(A). Similarly D_B: b,b'. Claim: max_{x in A, y in B} dist(x,y) = max( dist(a,b), dist(a,b'), dist(a',b), dist(a',b') ). Is this always true? I think yes. Reason: For any node x in A, consider the farthest node in A from x? Not directly. But we can use that for any node x in A, the farthest node in A is either a or a' (or both) if the diameter endpoints are a and a'? Actually, for any node in a tree, its farthest node(s) in a given set is one of the endpoints of the diameter of that set. This is a known property: For any set S in a tree, the farthest point from any given point p in the tree to S is either one of the endpoints of the diameter of S. Because consider the diameter endpoints u,v of S. For any node p, the farthest node in S from p is either u or v. This can be proven by considering the tree and distances: For any w in S, dist(p,w) ≤ max(dist(p,u), dist(p,v)). So indeed, for any p, the maximum distance to S is attained at one of the diameter endpoints. Apply this to p being any node y in B: the farthest node in A from y is either a or a'. So for fixed y, max_{x in A} dist(x,y) = max(dist(a,y), dist(a',y)). Therefore, max_{x in A, y in B} dist(x,y) = max( max_{y in B} max(dist(a,y), dist(a',y)) ) = max( max_{y in B} dist(a,y), max_{y in B} dist(a',y) ). Now, for the set B, the farthest node from a fixed node a is either b or b' (since a is a node, and B's diameter endpoints b,b' are farthest among B from any node?). Actually the property holds: For any node q, the farthest node in B from q is either b or b'. So max_{y in B} dist(a,y) = max(dist(a,b), dist(a,b')). Similarly for a'. Thus overall max = max of the four distances. So indeed the property holds. Great!
Thus, if we maintain for each color within a segment tree node the two endpoints of its diameter (or a representation of the set of nodes of that color in that segment), we can combine two child segments (which correspond to disjoint sets of nodes) by merging the two sets. For a given color, we have two sets from left and right children. The merged set's diameter can be computed from the four endpoints: the two endpoints of left's diameter and two endpoints of right's diameter. That's at most 4 nodes; we need to compute distances among these 4 nodes (pairwise) to find the farthest pair. So we can combine in O(1) using LCA to compute distances.
Thus we can build a segment tree over the Euler tour array. At each segment node, we store for each color (0 and 1) the following:
- Two nodes representing the diameter endpoints for that color within the segment. If there are no nodes of that color, we store something like null.
Also we need to handle lazy propagation for flipping colors in a subtree. Flipping colors for a segment means swapping the information for color 0 and color 1 for that segment. Because toggling parity means all nodes in that subtree have their color inverted. So we can have a lazy tag that indicates whether the colors for that segment should be swapped. When applying swap, we just swap the stored data for color0 and color1.
Now, we also need to know for each node in the Euler array its original vertex ID, and also its depth for distance computation. And we need LCA precomputation to compute distances quickly (O(1) with RMQ or binary lifting? Since n up to 500k, we can use Euler tour + RMQ for LCA with O(1) query, or binary lifting with O(log n) which might be okay if each segment combine does O(log n) distance queries? But we have many combine operations: each query (update) will need to update the segment tree along O(log n) nodes, and each combine for those nodes will need to compute distances O(1) each, but each distance computation may require LCA which we want O(1). So we need O(1) LCA. With n up to 500k, we can build a sparse table on Euler tour of size 2n-1; that's typical. Or we can use binary lifting with O(log n) but each update triggers O(log n) node updates, each requiring O(1) distances? Actually each combine may need to compute distances between up to 4 nodes; with binary lifting that's O(log n) per distance, leading to O(log^2 n) per node combine, which is too heavy for 500k updates. So O(1) LCA is advisable.
Alternatively, we could use centroid decomposition or something, but segment tree with LCA seems straightforward.
Plan:
-
Root the tree at node 1 (or any fixed root). Perform DFS to compute:
- Euler tour order (preorder) array
order[1..n](each vertex appears once in preorder). Actually we need to map each node to a position in the segment tree. So we assign each node an indexpos[node]from 1 to n based on preorder. depth[node](number of edges from root).tin[node],tout[node]for subtree range in the segment tree.- Also we need LCA: we can use Euler tour for LCA (the standard method: record the array of visited nodes during DFS (
euler[]) and depth of each visited node; then LCA(u,v) is node with minimum depth in the range between first occurrences of u and v in the euler array). We'll need a RMQ structure (sparse table) on that array. That works. But note that our segment tree positions are based on preorder, which is not the same as the Euler tour for LCA (which includes backtracking). We can have two different traversals: one for subtree ranges (preorder), and one for LCA (Euler tour with 2n-1 entries). That's fine.
- Euler tour order (preorder) array
-
Initially, compute parity for each node. Root at 1, parity[1] = 0. For each edge (u,v) with type t, we can compute parity for children during DFS. Actually we need to know for each edge, which side is child? Since we will later flip edges by index. We'll need to know for edge id, which node is the child (the one further from root) so that flipping toggles parity of subtree of child. So during DFS, we record for each edge id, the child node. We'll also need to know the direction relative to root: we can root the tree and for each edge, if u is parent of v, then child = v; else if v is parent of u, child = u. So we determine parent-child relationships.
For initial types, we assign parity accordingly: When traversing edge from parent to child, parity[child] = parity[parent] XOR type.
-
Build segment tree over nodes in preorder (size n). Leaf at position pos[node] stores information for that node only. For leaf, we have two colors: the node's color = parity[node] (0/1). So for that color, the diameter endpoints are (node, node) (distance 0). For the other color, there are no nodes (we represent as empty). We'll need a way to represent empty sets. We can store a boolean flag if set is non-empty, and endpoints.
In segment tree node, for each color we store:
- u (endpoint1)
- v (endpoint2)
- maybe also a boolean "has" indicating if there is at least one node. But we can also represent empty by setting u=v=-1 and dist = -inf. In combine, we need to handle empty sets appropriately.
Actually we might store just two endpoints, and if set empty, set both to -1. When merging, if one set is empty, the result is the other set's diameter.
-
For each segment tree node, we also have a lazy flag
swap(bool) indicating that the colors for that node's range should be swapped. -
Build segment tree: bottom-up combine children.
-
For each update: given edge id, we identify child node c (the node in the subtree to toggle). Then we need to flip colors for all nodes in subtree of c. That corresponds to range [tin[c], tout[c]] in preorder (tin/tout from DFS with preorder). We do a range update on segment tree: apply lazy swap on that range. Since flip is just swapping color 0 and color 1 information.
After update, we need to output answer = max( diameter_length(0), diameter_length(1) ), where these diameters are for the whole tree (root segment). So at the root of segment tree, we have stored for each color the diameter endpoints. The diameter length is dist(u,v) (if non-empty). If a color has fewer than 2 nodes, its diameter is 0? Actually if only one node, the path length is 0 (single node path, number of edges = 0). But is a path of length 0 valid? A simple path can start and end at the same village, which has 0 edges. The condition is that the number of stone edges is even, which for an empty path is 0 (even). So length 0 is valid. But we need maximum length; if there is at least one node, the diameter might be 0 if only one node. But we can have path with length >0 if there are at least two nodes of that color. However, we need to output maximal possible length of a path (number of edges) with even number of stones. So if there is at least one node, we can always take a single node path (length 0). But maybe there is longer. So answer should be max of diameters of both colors. If a color has 0 nodes? Both colors always have at least one node? Actually total nodes n, each node has a parity, so both colors are present unless all nodes same parity. So at least one node per color? Actually both colors could be present or not. If only one color exists, the other color has 0 nodes. But we can still consider empty set -> no path? A path must be a simple path between two villages, so at least one node? The path can start and end at same village, so if a color has at least one node, we have a path (single node). If a color has no nodes, we cannot form a path (since no village of that color). But answer will be from the other color. However, if a color has no nodes, its diameter length is 0? Actually we should treat as 0 because no path using that color exists (or maybe we consider length 0 from empty set? But it's fine to treat as 0 because max with the other color will be taken, and if both empty? That can't happen because n>=2 and at least one node exists. So we can define for empty set diameter length = 0.
But careful: The problem wants the maximal length of a simple path (number of edges) where number of stone edges is even. That is exactly the maximum distance between two nodes of same parity. If there is only one node of a given parity, the maximum distance for that parity is 0 (the path from that node to itself). So answer = max(max_distance(parity0), max_distance(parity1)). So we compute that.
So from segment tree root we have for each color either an empty set or a set with at least one node. For non-empty set, we can compute distance between its stored endpoints. But if the set has only one node, the endpoints will be the same node? We need to ensure that in leaf we set both endpoints to the same node. In combine, when merging sets, if a set has one node, its diameter endpoints are that node for both. The combine logic should handle correctly: when left set has one node and right empty, we take left's diameter (u,v same). So it's fine.
However, we also need to consider that the set may have multiple nodes but we might store endpoints that are same if only one node? Actually we need to represent the diameter as a pair of nodes; if only one node, we can set both to that node. The distance will be 0.
But is it possible that the set has multiple nodes but the diameter endpoints we store are not computed correctly because we only consider merging via four endpoints? The property holds that the diameter of union of two sets can be computed from the four endpoints of the diameters of the two sets. However, this assumes each set is non-empty. If a set is empty, we ignore it. For sets with one node, its diameter endpoints are that node (both same). The property still holds: For set with one node, the diameter endpoints are that node (both same). Then when merging, we consider up to 2 distinct nodes? Actually if left has one node a, right has one node b, then the four endpoints are (a,a) and (b,b). The maximum distance among all pairs from left∪right is dist(a,b). And our combine will consider distances between a and b (since we compute all pairwise distances among the set of up to 4 endpoints, which includes duplicates; but we should handle duplicates correctly). The max should be dist(a,b). So fine.
So the segment tree node's stored diameter endpoints for a color should represent the diameter of that color's nodes within that segment. For combine, we gather up to four candidate nodes: the two endpoints from left, two from right (if they exist). Then among all pairs (including pairs within left? but left's diameter is already the max within left, similarly right). So we need to consider the six pairs: left endpoints pair (already diam left), right endpoints pair (diam right), and cross pairs: each left endpoint with each right endpoint (four pairs). The maximum distance among these gives the diameter of the union. So we can compute.
Implementation: We'll have a function
dist(u,v)that returns number of edges between u and v using depth and LCA.For a segment tree node, we store for color 0: endpoints a0,b0 (maybe identical if single node). For color 1: a1,b1. And also maybe a flag indicating if empty. But we can treat empty as endpoints both -1 and we handle accordingly.
Since we need to compute distances many times (each combine up to 6 distances), we want O(1) per distance. We'll precompute depth and LCA structure.
-
After each update, we perform a range update on segment tree: apply swap on interval [tin[c], tout[c]]. Since this is a range flip, we can implement lazy propagation: for each node, we have a boolean
lazymeaning that the colors for that segment should be swapped. When we apply swap, we swap the data for color0 and color1, and toggle the lazy flag for children (i.e., if we have to push later). Actually we can store lazy as a boolean (0/1) indicating pending swap. When applying a swap to a node, we swap its stored color0 and color1 information, and set lazy ^= 1 (i.e., toggle). Then when pushing to children, we propagate the swap (i.e., apply same operation to children).Since updates are range flips, we can implement segment tree with range XOR lazy. Complexity O(log n) per update.
-
After updating, the root node's data gives diameters. We compute d0 = diameter length for color0 (if exists else 0), d1 similarly, answer = max(d0, d1).
Now we need to ensure that the initial parity assignment is consistent with updates. When we flip an edge (id), we toggle the type of that edge. In our model, we treat node colors (parity) as root XOR sum of edge types along path. Flipping an edge (u,v) toggles the parity of all nodes in the subtree of the child (assuming rooted). Let's verify:
Let root = 1. For each edge, we orient it from parent to child. Let child = c, parent = p. The parity of any node x in subtree of c is originally parity[x] = parity[p] XOR (sum of edge types along path from p to x). The path from root to x includes edge (p,c) and then rest. If we flip the type of edge (p,c), that changes the sum along that edge by toggling its contribution. So parity[x] becomes parity[x] XOR 1 for all x in subtree of c. So indeed toggling parity of all nodes in subtree of c is correct.
What about the case where the edge is between two nodes such that neither is the root? The parent-child relation is defined relative to root. So child is the one further from root. So flipping toggles subtree of child.
Now, after each flip, the edge type changes; but we don't need to explicitly store the type for future flips? Actually flips are independent; each update flips the current type. In our model, we maintain node colors via toggling subtrees. But does flipping the same edge again toggle again? Yes. So we just apply same range toggle each time. So we don't need to store edge types explicitly; we just need to know for each edge id which node is the child. That is fixed (since the tree is static; rooting is fixed). So we can precompute child for each edge.
But careful: When we flip an edge, we toggle the parity of all nodes in the child's subtree. However, does this correspond exactly to the effect of flipping the edge type? Let's double-check with an example where the edge is not incident to root. Suppose we have root = 1, edge between nodes 3 and 5, with parent 3, child 5. Parity[5] = parity[3] XOR type(3-5). Flipping type toggles type, so new parity[5] = parity[3] XOR (type XOR 1) = old parity[5] XOR 1. For any descendant x of 5, parity[x] includes that edge, so toggles as well. So toggling subtree of child works. Good.
Thus we have a correct mapping.
Now the key is building the segment tree with initial colors.
But we must ensure that the answer we compute (max distance between same parity nodes) corresponds to the longest path with even number of stone edges. Let's confirm: For a path between u and v, # stone edges = sum_{edges on path} type = parity[u] XOR parity[v] (mod 2). Actually careful: parity is sum mod 2 from root. Then sum along path u-v = (parity[u] XOR parity[v]) if using XOR? Let's compute: parity[u] = sum(root to u) mod2. parity[v] = sum(root to v) mod2. The sum along path u-v = (parity[u] XOR parity[v])? Because sum(root to u) + sum(root to v) mod2 = parity[u] + parity[v] (mod2). But the edges from root to LCA are counted twice, which mod2 cancels. Actually sum along path u-v = (parity[u] + parity[v] - 2parity[lca]) mod2 = parity[u] + parity[v] mod2 (since 2anything is 0 mod2). So parity[u] + parity[v] mod2 = parity[u] XOR parity[v] (since mod2 addition is XOR). So indeed parity[u] XOR parity[v] gives parity of number of stone edges. For even (0 mod2), we need parity[u] = parity[v]. So condition matches.
Thus our approach is correct.
Now we must implement segment tree with these capabilities.
Let's outline the data structures:
- n up to 500k, so segment tree size 4*n ~ 2M, which is okay.
- We'll store for each node in segment tree: two pairs (endpoint1, endpoint2) for color0 and color1, and lazy flag.
But we also need to compute distances quickly. We'll use LCA with Euler tour + RMQ.
Simplify: Use binary lifting with O(log n) maybe still okay if we have 500k updates * log n (~20) * each combine does up to 6 distances = 120 distance computations per node combine? Actually each update triggers O(log n) nodes being updated (range update) and for each node we need to recompute its values after pushing lazy or after children update. In a segment tree with lazy propagation, during an update we traverse down the tree to cover the range, applying lazy at nodes fully covered, and then on the way back we recompute (pull) the values for each visited node. So number of nodes visited is O(log n) for the update (the path nodes), but we also need to recompute for each node on the path. So total node updates O(log n). For each node recompute, we need to combine its two children. That combine involves for each color, merging two child's color info. So for each node we need to compute at most two merges (color0, color1). Each merge involves considering up to 2 endpoints from left and 2 from right, total up to 4 nodes, compute distances among them (up to 6 distances). Each distance requires LCA query, which we aim to be O(1). So per node combine constant time. So total per update O(log n). With m up to 500k, that's ~500k * log2(500k) ~ 500k * 19 = 9.5M operations, which is fine.
But we also need to consider the overhead of building the segment tree initially O(n). So overall feasible.
Memory: segment tree node can store for each color two vertex indices (int) and maybe a boolean "exists". But we can use -1 to indicate empty. For lazy: bool.
Thus we can define:
struct Node { int c0_u, c0_v; // endpoints for color0; if c0_u == -1 then empty. int c1_u, c1_v; bool lazy; // whether to swap colors };
But we need to store also maybe the diameter length? Not necessary; we can compute distances on the fly when needed for answer. But for merging we need to compute distances between endpoints, so we need to compute distances many times. We could store distances along with endpoints to avoid recomputing? But distance computation is O(1) with LCA, so fine.
However, merging requires comparing distances; we will compute distances for candidate pairs.
Implementation details:
Define function
int dist(int u, int v): if u == -1 or v == -1: return -INF (or ignore) use LCA to compute depth[u] + depth[v] - 2*depth[lca(u,v)].But we also need to handle u == v: dist = 0.
We'll precompute depth array and first occurrence index in Euler tour for LCA.
For LCA, we can generate an Euler tour array
eulerof length 2n-1 (or 2n) and an arraydepth_eulerof same length, andfirst[u]= first occurrence index. Then build RMQ (sparse table) overdepth_eulerto query min depth index in a range. But building sparse table O(N log N) with N = 2n ~1e6, which is okay (1e6 * 20 = 20e6). Alternatively use segment tree for RMQ but O(log n) per query. Sparse table gives O(1) query but requires O(N log N) memory: 1e6 * 20 = 20 million ints, maybe okay (80 MB) but borderline. 500k nodes gives euler length 2500k-1 = 999,999 ~ 1e6. Sparse table with int indices of size 1e6 * 20 = 20e6 entries, each 4 bytes -> 80 MB. Plus other arrays, could be okay but might be high. We could use binary lifting for LCA with O(log n) per query; that would add log factor to each distance, leading to O(log^2 n) per combine, which might be okay? Let's compute: updates 500k, each update needs O(log n) node combines, each combine does up to 6 distances -> 6 * log n per combine? Actually each distance using binary lifting O(log n). So per update O(log^2 n) ~ 19^2 = 361 * 500k = 180M, maybe borderline but possibly pass in C++ with optimization. But we might prefer O(1) LCA to be safe.Alternative: Use Euler tour + RMQ with a segment tree for RMQ (O(log n) per query). That would also be O(log n) per distance. So similar.
We could use the method of "binary lifting with O(1) query via technique of Farach-Colton and Bender (Sparse Table on Euler tour) which is typical.
Given constraints (500k), we can use the Euler tour + RMQ with a sparse table. Memory 80 MB is acceptable? But we also have segment tree ~ 4n * (4 ints + bool) ~ 4500k * (about 4*4=16 bytes) = 32 MB. Plus other arrays. Total maybe 120-150 MB, which may be okay for typical memory limit 256 MB. But we must be careful.
Alternatively, we can use "binary lifting with O(1) using precomputed masks for small blocks" (the +/-1 RMQ) but that's more complex.
We can also note that distance queries are only among nodes that appear as endpoints in segment tree. In total, number of distance computations is at most about (6 * number of node updates). Number of node updates: each update visits O(log n) nodes, and building initial tree processes O(n) nodes. So total distance calls ~ O((n+m) log n) ~ 10 million. O(10M * log n) if LCA O(log n) would be ~200M operations, which might be okay in C++ if optimized, but perhaps safer to aim for O(1).
Given that we have to implement efficiently, I'll go with Euler tour + RMQ using sparse table.
But careful: We need to map vertex id to depth. We already have depth from root (for distance: depth[u] + depth[v] - 2depth[lca]). We can compute depth from root easily. For LCA we need the Euler tour of the tree: we do DFS, record vertex when we enter, and also when we exit? Usually for LCA we record each time we visit a node (on entry and when backtracking). The length is 2n-1. We'll store an array
euler_tour[0..2*n-2]of vertices visited. Andfirst_occurrence[u]the index of first occurrence. Also we storedepth[u]from root (number of edges). Then for LCA(u,v), we find indices l = first[u], r = first[v], if l > r swap, then query RMQ ondepth_eulerover [l, r] to get the vertex with minimum depth (i.e., the LCA). The RMQ returns the index of minimal depth. We'll store the Euler tour and build sparse table on the array of depths (or on the array of vertices with comparator based on depth). Usually we store an array of vertices and a separate array of depths for each position. The sparse table stores the index of the vertex with minimum depth for each interval.Simplify: We can store
euler_depth[pos]= depth[euler[pos]]. Then we want RMQ that returns the position with minimum depth. Then LCA = euler[pos_min]. So we need a sparse table over indices of the euler array.Implementation steps:
-
Run DFS from root (1):
parentfor each node, but not needed for LCA if we use Euler.depth[node](int)tin[node]for preorder (for segment tree) (starting from 0 or 1)tout[node]for subtree end.parity[node]computed.- For LCA: maintain
eulerlist,first[node]. - For each node when we first visit, push to euler, and also when we finish a child we push the node again? Standard algorithm: In DFS, when we enter node, we append node to euler; after processing each child, we append node again. But we only need the first occurrence for LCA queries. We'll use the typical approach:
function dfs(u, p): tin[u] = ++timer; // preorder index euler.push_back(u); first[u] = euler.size() - 1; for each v in adj[u]: if v != p: depth[v] = depth[u] + 1; parity[v] = parity[u] xor type(u,v); dfs(v, u); euler.push_back(u); tout[u] = timer;
This yields euler size = 2*n-1. The preorder timer gives each node a unique index from 1 to n.
Also record for each edge id, the child. While doing DFS, for an edge (u,v) with type t, if we go from u to v (v not parent), then we know child = v for that edge. We'll store child[edge_id] = v.
We also need initial parity values based on initial edge types. During DFS we compute parity using given edge types.
So after DFS we have:
- preorder index
pos[u]= tin[u] (or a separate array). - subtree range: [tin[u], tout[u]] inclusive.
We'll also build an array
aof size n, where a[tin[u]] = parity[u]? Actually we need leaf information: at leaf (position corresponding to node u), we store that node u belongs to color parity[u]. But in the segment tree, we store for each leaf the diameter endpoints for each color. Since leaf has only one node, we set for that leaf: if parity[u]==0 then color0 has endpoints (u,u) and color1 empty; else color1 has (u,u) and color0 empty.So we can build segment tree over positions 1..n (preorder). Leaf i corresponds to node
node_by_pos[i].We need a mapping from position to node id:
rev[i] = uwhere tin[u] = i.That's it.
Segment tree implementation:
We'll implement a class SegTree with arrays for c0_u, c0_v, c1_u, c1_v, lazy. Or we can store as a struct and use vector.
Define a function
mergethat given two nodes (left and right) returns a new node with combined info. But careful: The combine operation should merge the sets of nodes from left and right intervals (which are disjoint sets of vertices). For each color, we need to merge the two sets.Pseudo:
struct Info { int u0, v0; // endpoints for color0, -1 if none int u1, v1; // for color1 };
Info merge(Info a, Info b) { Info res; // combine color0 res.u0 = res.v0 = -1; if (a.u0 == -1 && b.u0 == -1) { // empty } else if (a.u0 == -1) { res.u0 = b.u0; res.v0 = b.v0; } else if (b.u0 == -1) { res.u0 = a.u0; res.v0 = a.v0; } else { // both non-empty // candidate endpoints: a.u0, a.v0, b.u0, b.v0 // we need to find pair (x,y) among these 4 that maximizes dist(x,y) // also we need to consider the individual diameters: a's diameter and b's diameter are already max within each, but they are among candidates anyway // So we can compute max distance among all pairs. // However, note that a.u0 and a.v0 might be same (if only one node). It's okay. vector cand = {a.u0, a.v0, b.u0, b.v0}; int best_dist = -1; int best_u = -1, best_v = -1; // also consider case where a's diameter or b's diameter might be larger than cross? We'll check all 6 pairs. // Actually we need to consider pairs: (a.u0, a.v0), (b.u0, b.v0), and cross: (a.u0,b.u0), (a.u0,b.v0), (a.v0,b.u0), (a.v0,b.v0) // So we can evaluate these six distances. // However, note that if a has only one node, a.u0 == a.v0, so some pairs duplicate, but that's fine. // We'll compute distances for these pairs and pick max. // We'll implement a helper to update best. // Then set res.u0, res.v0 to the pair giving max distance. // But we also must ensure that if both sets have nodes but maybe all nodes are same? distance zero. } // similarly for color1 // ... return res; }
But we need to compute dist many times. We'll implement a function
int get_dist(int u, int v)that returns distance if u!=-1 and v!=-1 else -1.But careful: In merge, we need to treat empty sets correctly. For color0: if one side empty, result is the other side's endpoints. If both non-empty, compute as described.
But note: The diameter endpoints we store for a set are not necessarily unique; but they represent the farthest pair. The property that union diameter is among the four endpoints holds if the sets are non-empty. So we can compute using the four endpoints.
We need to be careful: Suppose a set has only one node: we store u0=v0= that node. Then the four endpoints are that node (twice) and the two from other set. The cross pairs will include duplicates? For cross pair (a.u0, b.u0) and (a.v0, b.u0) are same if a.u0==a.v0. That's fine.
Implementation: In merge, for each color, gather a list of up to 2 distinct candidate nodes from each child? Actually we should consider the endpoints from each child. They might be the same node if the child set is a single node. But we can just take the two endpoints (maybe same). So we have up to 4 nodes. However, the diameter of the union could also be the diameter of left or right itself, which is included in the candidate pairs: (a.u0, a.v0) and (b.u0, b.v0). So we can compute all six pairs as described.
Alternatively, we can compute the farthest pair by considering all combinations of the up to 4 nodes, but that's at most 6 pairs. That's fine.
Now, we also need to handle the case where one of the sets is empty: then the result is just the other set's diameter.
Implementation details:
Define a function
pair<int,int> combine_two(Info left, Info right, int color)but we can implement generic.Pseudo:
// given two endpoints sets for a color from left and right: pair<int,int> merge_color(int u1, int v1, int u2, int v2) { // u1,v1 may be -1 for empty; if both -1 return (-1,-1) if (u1 == -1 && u2 == -1) return {-1, -1}; if (u1 == -1) return {u2, v2}; if (u2 == -1) return {u1, v1};
// candidates: vector<int> nodes = {u1, v1, u2, v2}; // we will evaluate distances for pairs: // (u1,v1), (u2,v2), (u1,u2), (u1,v2), (v1,u2), (v1,v2) int best_dist = -1; int best_u, best_v; auto consider = [&](int x, int y) { if (x == -1 || y == -1) return; int d = dist(x, y); if (d > best_dist) { best_dist = d; best_u = x; best_v = y; } }; consider(u1, v1); consider(u2, v2); consider(u1, u2); consider(u1, v2); consider(v1, u2); consider(v1, v2); return {best_u, best_v};}
But note: This works even if u1==v1 or u2==v2.
Now, Info struct has both colors. So in merging two Info nodes, we need to produce Info where c0 = merge_color(left.c0, left.c0v? Actually left.c0_u, left.c0_v with right.c0_u, right.c0_v) and similarly for c1.
We also need to incorporate the effect of lazy swap when pushing. But we'll handle that in update functions.
Now, segment tree implementation:
We'll build tree over positions 1..n. We'll store arrays:
vector c0_u, c0_v, c1_u, c1_v; vector lazy; // or int as 0/1.
We can use iterative segment tree? Range updates with lazy require recursive or segment tree with push. Since n up to 500k, recursion depth O(log n) is fine but we need to be careful with recursion in DFS and segment tree functions. Use iterative? But recursive segment tree with lazy is easier to implement correctly.
I'll implement a recursive segment tree class with functions build(l, r, idx), update_range(ql, qr, idx), push(idx). Since n large, recursion depth for segment tree is about 2*log2(n) ~ 40, safe. But we need to avoid stack overflow due to deep recursion in building (which is okay). However, the total number of function calls for m updates could be high but each update does O(log n) recursive calls. That's okay.
Alternatively, we can implement an iterative segment tree with lazy propagation (like using arrays and loops) but more complex for range flips. I'll stick with recursive.
Memory: 4n arrays of ints (c0_u, c0_v, c1_u, c1_v) => 4 * 4 * n? Actually 4 arrays of size 4n? We'll allocate size 4n. For n=500k, 4n=2e6, times 4 arrays = 8e6 ints, ~32 MB. Plus lazy array of bool (2e6) ~2 MB. Plus other arrays. Acceptable.
Now, LCA sparse table:
We'll have:
vector euler; // size about 2*n vector depth; // depth per node vector first; // first occurrence in euler vector log2; // precomputed logs vector<vector> st; // sparse table storing indices of min depth
We need to be able to compute lca(u,v) fast.
Implementation:
DFS:
dep[u]= depth from root (edges count)tin[u]= ++timer (preorder, 1-indexed)rev[timer] = ufirst[u] = euler.size()euler.push_back(u)- For each child v:
- dfs(v)
- euler.push_back(u)
After DFS, we have euler array of length L = 2n - 1 (if we push u after each child and after finishing? Actually as above, we push u when we first enter, and after returning from each child we push u again. So length = 2n -1.
Then we build sparse table over array
depthcorresponding to euler positions: we need an arrayeuler_depth[i] = dep[euler[i]]. Then RMQ: For any l <= r, we want index i in [l,r] with minimum euler_depth[i]. We'll store in sparse table the index of minimum depth for intervals of length 2^k. We can precompute log2 for up to L.Memory: L up to 1e6. log2[L+1] precomputed. st[k][i] for k up to floor(log2(L)), about 20. So st size L*20 ~ 20e6 ints, 80 MB. Acceptable.
But we can reduce memory by using vector of vectors; 20e6 ints = 80 MB; plus other arrays maybe total ~150 MB, which should be okay for typical 256 MB limit. But we need to be careful with memory usage in C++: using vector<vector> may have some overhead; we can use a single vector and compute index manually: st[k][i] stored in a 2D array as vector<vector>(K