Kuro is living in a country called Uberland, consisting of n towns, numbered from 1 to…
- User
Kuro is living in a country called Uberland, consisting of n towns, numbered from 1 to n, and n - 1 bidirectional roads connecting these towns. It is possible to reach each town from any other. Each road connects two towns a and b. Kuro loves walking and he is planning to take a walking marathon, in which he will choose a pair of towns (u, v) (u ≠ v) and walk from u using the shortest path to v (note that (u, v) is considered to be different from (v, u)).
Oddly, there are 2 special towns in Uberland named Flowrisa (denoted with the index x) and Beetopia (denoted with the index y). Flowrisa is a town where there are many strong-scent flowers, and Beetopia is another town where many bees live. In particular, Kuro will avoid any pair of towns (u, v) if on the path from u to v, he reaches Beetopia after he reached Flowrisa, since the bees will be attracted with the flower smell on Kuro’s body and sting him.
Kuro wants to know how many pair of city (u, v) he can take as his route. Since he’s not really bright, he asked you to help him with this problem. Input
The first line contains three integers n, x and y (1 ≤ n ≤ 3 ⋅ 10^5, 1 ≤ x, y ≤ n, x ≠ y) - the number of towns, index of the town Flowrisa and index of the town Beetopia, respectively.
n - 1 lines follow, each line contains two integers a and b (1 ≤ a, b ≤ n, a ≠ b), describes a road connecting two towns a and b.
It is guaranteed that from each town, we can reach every other town in the city using the given roads. That is, the given map of towns and roads is a tree.
Output
A single integer resembles the number of pair of towns (u, v) that Kuro can use as his walking route.
Examples
Input
3 1 3 1 2 2 3
Output
5
Input
3 1 3 1 2 1 3
Output
4
Note
On the first example, Kuro can choose these pairs:
- (1, 2): his route would be 1 → 2,
- (2, 3): his route would be 2 → 3,
- (3, 2): his route would be 3 → 2,
- (2, 1): his route would be 2 → 1,
- (3, 1): his route would be 3 → 2 → 1.
Kuro can't choose pair (1, 3) since his walking route would be 1 → 2 → 3, in which Kuro visits town 1 (Flowrisa) and then visits town 3 (Beetopia), which is not allowed (note that pair (3, 1) is still allowed because although Kuro visited Flowrisa and Beetopia, he did not visit them in that order).
On the second example, Kuro can choose the following pairs:
- (1, 2): his route would be 1 → 2,
- (2, 1): his route would be 2 → 1,
- (3, 2): his route would be 3 → 1 → 2,
- (3, 1): his route would be 3 → 1.
Assistant
We need to solve: Given a tree of n nodes, two distinct nodes x and y (Flowrisa and Beetopia). We need to count number of ordered pairs (u, v) with u != v such that on the shortest path from u to v, we do NOT encounter x (Flowrisa) and then later y (Beetopia). More precisely: "he will avoid any pair of towns (u, v) if on the path from u to v, he reaches Beetopia after he reached Flowrisa, since the bees will be attracted with the flower smell on Kuro’s body and sting him." So forbidden is when the path from u to v contains both x and y, and the order of traversal (starting from u) includes x before y. i.e., the path goes through x and later through y. Note that if it goes through y before x, it's allowed. Also if it doesn't contain both, it's allowed.
We need count allowed ordered pairs.
Total ordered pairs = n*(n-1). Subtract forbidden pairs.
Thus we need to count number of ordered pairs (u, v) with u != v such that the path from u to v visits x then y in that order.
Observations: The tree is a tree, unique simple path between any two nodes.
The path from u to v will contain both x and y if and only if u and v lie in different "components" relative to the x-y connection? Actually, the path will contain both x and y when the unique simple path between u and v includes the segment between x and y. More precisely, in a tree, if we remove the edge(s) along the path between x and y, we break the tree into components. But careful: The unique simple path between u and v will include both x and y if and only if u is in one side of the x-y path (including possibly x or y) and v is on the other side, and also the order? Actually, to include both x and y, the path must go through the entire path between x and y. That occurs if u and v are in different "subtrees" when we consider the tree as rooted at something? Classic problem: For two nodes x and y, the nodes whose path contains both are those where one is in a certain subtree not containing the other? Let's think.
Given two distinct nodes x and y, consider the simple path P from x to y. For any two nodes u, v, the path from u to v will contain both x and y if and only if x and y lie on the path between u and v. That condition can be expressed as: u and v are in different connected components after removing all nodes on the path P? Actually, we need to think about the condition for x to lie on the path between u and v: That is when u and v are in different subtrees of the tree when we root at x (i.e., x separates u and v). Similarly for y to lie on the path. For both x and y to lie on the path, we need that the path from u to v passes through both. This means that u and v are on opposite sides of the edge(s) that connect the components containing x and y? Let's formalize.
Define the tree. The unique path between u and v is the set of nodes along the way. For x and y to both lie on this path, it must be that the path from u to v goes through x and y. Since the tree is acyclic, the path from u to v is the concatenation of the path from u to x, then from x to y, then from y to v (or possibly u to y to x to v if order reversed). But the order along the path depends on positions.
Actually, there are two possibilities: either the path from u to v goes through x then y (order u ... x ... y ... v) or goes through y then x (order u ... y ... x ... v). Both have both nodes. However, we care about the direction: from start u to v, if we encounter x then later y, then it's forbidden. So if the path includes both, we need to check order.
Thus we need to count ordered pairs (u,v) such that the path from u to v includes both x and y, and along the direction from u to v, x appears before y.
We could count total pairs that include both, then half? Not exactly because the distribution of u and v relative to the x-y line matters.
Think about the tree structure: Remove the edge(s) along the path from x to y? Actually, the path from x to y might consist of multiple edges. But we can treat the unique simple path between x and y. Consider breaking the tree by removing the edge that is adjacent to x on the path to y? Or consider the tree rooted at x? Need a systematic way.
Alternative approach: Forbidden pairs are those where: x is on the path from u to v, and y is also on that path, and the distance from u to x < distance from u to y (i.e., x is encountered before y). Since the path is unique, if both are on the path, one of them is closer to u than the other. So condition is simply dist(u, x) < dist(u, y). Because if both are on the path, the order from u is determined by distances to u. Indeed, along the simple path from u to v, nodes are encountered in increasing order of distance from u (along the path). So if x and y are both on the path, then we encounter the one with smaller distance from u first. So forbidden if dist(u, x) < dist(u, y) and both are on the path.
But careful: Could it happen that both are on the path but distances equal? Since x != y, distances from u to x and to y can be equal only if u is equidistant, which would mean that the path from u to v passes through some node? Actually if both are on the path, the distances from u to x and to y cannot be equal unless x = y? Because if both lie on the path, the distances from u to them are distances along that path. Since the path is simple, if distances equal, then x and y would be the same node (since at a given distance from u on that path there's exactly one node). So they can't be equal. So indeed, one is strictly smaller.
Thus forbidden condition: (x lies on path u->v) AND (y lies on path u->v) AND (dist(u, x) < dist(u, y)).
Similarly, allowed: if either x not on path or y not on path, or if both on path but dist(u, y) < dist(u, x) (i.e., y before x).
Thus we can compute total ordered pairs minus those where both on path and dist(u,x) < dist(u,y). That seems simpler to count.
But counting directly based on distances might be tricky. However, we can think in terms of tree structure relative to x and y.
Observation: For both x and y to be on the path from u to v, the path must "cover" the segment between x and y. This essentially means that u and v are in different "branches" relative to the x-y axis: one is in the component containing x when we cut the edge(s) that separate x and y? Let's define.
Consider the tree. The unique simple path between x and y. If we remove all edges on this path, the tree would split into several components? Actually, removing the edges of the path will break the tree into a set of subtrees attached to each node on the path. But a simpler approach: The condition that both x and y lie on the path from u to v is equivalent to: u and v are in two different components of the tree after removing the edge between ...? Let's recall known combinatorial property: For two fixed nodes a and b, the set of unordered pairs {u, v} such that the path between u and v contains both a and b can be counted as: If we root the tree at a, the nodes that are not in the subtree of b? Hmm.
Better: Consider the tree and the unique path P = (x = p0, p1, p2, ..., pk = y). For each node pi on the path, consider the "branch" (subtree) hanging off pi that does not include other nodes of P. That is, if we remove all nodes of P (or edges of P), the tree decomposes into connected components, each attached to a unique pi (since any node not on P is connected to P via a unique nearest pi). Let's denote for each pi, the size of its "branch" (including pi? Usually we include the node itself? We'll define precisely later.)
Now, for u and v such that the path includes both x and y, u must be in the branch of some pi, and v in the branch of some pj, and the path from u to v goes along P from pi to pj covering the whole segment. But it will include both x and y only if the interval from pi to pj covers the endpoints x and y, i.e., pi is on one side of P relative to x and y, and pj on the other side such that the segment between pi and pj includes both x and y. More concretely, if we consider the order along P from x to y, then for the path between u and v to include both x and y, u must be in a branch of some pi with index i, and v in a branch of some pj with index j, such that i <= 0? Actually indices from 0 to k. For it to include x and y, the path from u to v must go through all of P from x to y. That means that the smallest index among {i, j} must be 0 (i.e., x's side) and the largest must be k (i.e., y's side). Because if both i and j are, say, between 0 and k, then the path between them might not include both endpoints. For instance, if both u and v are attached to nodes between x and y, the path between u and v might only cover a subsegment of P, possibly missing x or y. To include both x and y, we need that one of u or v lies in the region that is on the x-side of x (i.e., the branch that includes x and beyond x away from y) and the other lies on the y-side of y (i.e., branch that includes y and beyond y away from x). More formally, consider the tree as if we cut the edge between x and its neighbor on the path to y? Actually, x is on the path. For the path from u to v to include both x and y, u must be in the component that contains x when we remove the edge on the path adjacent to x that goes toward y? Let's define:
Take the edge (x, next) on the path from x to y. If we remove this edge, the tree splits into two components: one containing x (call component A) and one containing y (component B). For the path to contain both x and y, u and v must be in different components? Not exactly, because u could be in A and v in B, then the path from u to v must go through that edge, and thus will include both x and y? Wait, if u is in A and v in B, the path will go from u to x (since x is in A) then from x across the edge to the next node, eventually to y and to v. So it will definitely include both x and y. Conversely, if both u and v are in A, the path between them will be entirely within A, and since y is not in A, the path cannot include y (unless u or v is x? But if both in A, the path may include x if x lies between them, but y is not in A, so y is not on the path). Similarly both in B cannot include x. Thus for both x and y to be on the path, u and v must be in different components after cutting the edge (x, next) i.e., the first edge on the path from x to y. However, is that sufficient? Consider u in A, v in B: path includes the edge (x, next), so it includes x, then goes to next, ... eventually to y. Does it necessarily include y? Yes, because to go from u in A to v in B, you must cross the unique edge connecting A and B. That edge is (x, next). After crossing, you are in B, and the path proceeds to v. But does it necessarily pass through y? Not necessarily: what if y is not on the route from next to v? Wait, we defined B as the component containing y when we cut that edge. B includes y and everything on the other side. But the path from next to v within B may or may not pass through y. For the overall path from u to v to include y, we need that y is on the path from next to v. However, since we are crossing at the edge (x, next), the path within B is from next to v. It will include y only if y lies on that path. But is it guaranteed that y lies on the path from next to any node v in B? No, not necessarily. For example, consider tree: x connected to next, next connected to y and also to some other node w. If v = w, then the path from u in A to v goes: u...x->next->w. That does not include y. So the condition that u and v are in different sides of the edge (x, next) is not sufficient to guarantee y is on the path. Similarly, x might not be on the path if u is not necessarily in A? Actually if u is in A, x is in A, but path from u to v goes through x only if x lies on the path from u to the cut edge. Since we cross at the edge (x, next), the path from u to that edge must go through x because x is the endpoint of that edge in A. For any node in A, the unique path to any node in B must include x, because to go from A to B you must cross that edge, and the node on A side of that edge is x. However, if u is not x, the path from u to that edge might not go through x if there is some other route? But the edge (x, next) is the only connection between A and B. So the path from u (in A) to any node in B will go to x then along the edge. Actually, is it always true that the path from u to the edge goes through x? Since the edge has endpoint x on A side, any path from u to a node in B must cross that edge. The point at which you enter the edge from the A side could be either x or maybe you could approach the edge from the other side? No, the edge is between x and next. So the A side of the edge is exactly the node x. Thus the path from u to B must go through x (the A endpoint) because you need to be at x to traverse that edge. However, what if u is in A but the path to B could go through some other edge that connects A and B? But we cut only that specific edge, and we defined A and B as the two components after removing that edge. By definition, there is no other connection between A and B. So any path from u in A to v in B must cross that unique edge, and thus must go through x (since from A side you must be at x to cross). So x is always on the path. So for u in A, v in B, the path always includes x. But does it always include y? Not necessarily. For y to be on the path, we require that the path from next to v includes y. Since v is in B, the path from next to v may or may not go through y. Thus condition for both x and y is stricter: we need that v lies in the component of B such that the path from next to v passes through y. In other words, v must be in the part of B that is "beyond y" from next's perspective? More systematically, we need to consider the tree relative to the whole path between x and y.
To include both x and y, u and v must lie in the two "outer" sides: one in the component that contains x when we cut the edge adjacent to x on the path to y, but also we need that the other node lies in the component that contains y when we cut the edge adjacent to y on the path to x. Moreover, they must be such that the path goes through the entire segment from x to y.
Thus, we can define:
-
Let the unique simple path between x and y be P = [x = p0, p1, p2, ..., pk = y].
-
For each node pi (0 ≤ i ≤ k), define the "branch" of pi as the set of nodes that are in the component containing pi when we remove all edges of P (i.e., cut off the path). More precisely, if we consider the tree, and remove all edges of P (there are k edges: (p0,p1), (p1,p2), ..., (p_{k-1}, pk)), then the tree breaks into k+1 connected components? Actually, each removal of edges yields a forest. The nodes of P are each in separate components if we remove edges? Wait, if we remove the edges of P, the path nodes become isolated? Not exactly: Because we remove only the edges that are on P, but each pi still may have other edges to branches. Since we remove all edges of P, the nodes p0,...,pk become disconnected from each other, but each pi remains connected to its own "branch" (the subtrees attached to it not using P edges). So we get for each pi a component that includes pi and all nodes reachable without using any edge of P. These are disjoint sets covering all nodes because any node not on P is attached via a unique pi (the first node on P encountered when moving from that node towards the path). So indeed, the node set V is partitioned into k+1 sets: one for each pi (including pi itself). Let's denote S_i = set of nodes whose nearest node on P is pi (or equivalently, the component containing pi after removing all edges of P). Note that S_i includes pi.
Now, consider any two nodes u and v. The unique path between them will include some segment of P. The path will include both x (=p0) and y (=pk) iff the path from u to v covers the entire P from p0 to pk. That happens exactly when u is in S_i for some i and v is in S_j for some j, and i <= 0? Actually, we need that the path from u to v goes from u to pi (using branch), then along P from pi to pj, then from pj to v. To cover both endpoints, we need that pi is on one side (i small) and pj on the other side such that the segment from pi to pj includes p0 and pk. In terms of indices, if i <= j, then the covered segment is from pi to pj. For it to include both p0 and pk, we need pi ≤ 0 (i.e., i = 0) and pj ≥ k (i.e., j = k) ? Wait indices are from 0 to k. The segment from pi to pj includes p0 and pk only if pi <= 0 and pj >= k, but since indices are bounded, this forces i = 0 and j = k (or i = k and j = 0 if reversed). Actually, if we consider order along P, to include both endpoints, the path must go from one endpoint to the other. That means that one of u or v must be in S_0 and the other in S_k? Not exactly: Suppose u is in S_0 (the component containing p0) and v is in S_k (component containing pk). Then the path from u to v: from u to p0 (via its branch), then along P from p0 to pk, then from pk to v. That certainly includes both p0 and pk. Conversely, if u is in S_0 and v is in S_{k-1}, the path goes from u to p0, then along P to p_{k-1}, then to v. That includes p0 but does not include pk because the segment ends at p_{k-1}. So pk is not on the path unless v is in S_k. Similarly, if u is in S_1 and v in S_k, path includes p1 to pk, missing p0. So indeed, for both x and y to be on the path, one node must be in S_0 and the other in S_k. Is that necessary and sufficient? Let's test: Could both nodes be in S_0 and still the path include both x and y? If both u and v are in S_0, the path between them stays within S_0 (since S_0 is connected and doesn't contain y unless y is also in S_0, but y is not because y is pk, and pk is in S_k, distinct). So cannot include y. Similarly both in S_k cannot include x. What about u in S_0 and v in S_i for some i not 0 nor k? Then the path goes from u to p0, then along P up to pi. Since i < k, pk not included. So y not on path. Similarly u in S_i (i not 0) and v in S_k: x not included. What if u in S_i and v in S_j with 0 < i < j < k? Then path includes only pi...pj, missing endpoints. So indeed, both endpoints appear only if one is in S_0 and the other in S_k.
Thus the condition for both x and y to be on the path is: u ∈ S_0 and v ∈ S_k OR u ∈ S_k and v ∈ S_0.
That's a nice simplification. Let's verify with the earlier edge-cut reasoning: if we cut the edge (x, p1), we got components A (contains S_0 and possibly more? Actually S_0 is exactly the component containing x after removing all P edges? Let's check: After removing all P edges, S_0 is the component containing p0 (x). If we only cut the first edge, A would be larger than S_0 because it includes all nodes attached to p1 as well except those beyond? Actually, if we cut only edge (x,p1), the component containing x would include all nodes that are reachable from x without using that edge. That includes S_0 and also maybe the rest of the tree beyond p1 if there are alternative paths? But in a tree, any path from x to nodes beyond p1 must go through that edge, so cutting it isolates x's component as exactly S_0? Let's think: After removing edge (x,p1), the component containing x includes all nodes that can be reached from x without crossing that edge. Since the only way to leave x's immediate neighborhood is via edges incident to x. Among those edges, one is (x,p1) (which is cut). Any other edges from x go to branches that are part of S_0. So indeed, the component containing x after cutting (x,p1) is exactly S_0 (the set of nodes that are in the branch attached to x excluding the rest of the path). Similarly, the component containing p1 includes everything else, including S_1,...,S_k. So A = S_0, B = union of S_1..S_k. Then the condition u in A and v in B yields that x is on the path, but y may not be. Because v could be in S_1 which is adjacent to p1 and not include y. So to ensure y is on the path, we further need that v is in the component that contains y when we cut the edge (p_{k-1}, y). That component is S_k. So indeed, the intersection of the two conditions (u in S_0 and v in S_k) is the only way to guarantee both.
Thus, for both x and y to be on the path, the ordered pair (u,v) must have u in S_0 and v in S_k, OR u in S_k and v in S_0.
Now, among those pairs, which ones are forbidden? Forbidden when the path from u to v encounters x before y. So we need to check order. For pair (u in S_0, v in S_k): start u (somewhere in S_0). The path goes from u to x (since x is in S_0; note that u could be x itself). Then from x along P to y, then to v. So along this route, we encounter x first, then later y. So this order is x then y. So for such (u,v), we have dist(u,x) < dist(u,y) (since x is encountered earlier). So it's forbidden. For pair (u in S_k, v in S_0): start u in S_k, path goes u -> y -> ... -> x? Actually careful: The path from u (in S_k) to v (in S_0) goes from u to y (since y is in S_k), then along P from y to x (reverse direction), then to v. So in this direction, we encounter y first, then later x. So the order is y then x, not forbidden. So only pairs where u is in S_0 and v is in S_k are forbidden. The reversed order (u in S_k, v in S_0) is allowed.
Therefore, the number of forbidden ordered pairs = |S_0| * |S_k|.
But is that all? Let's double-check edge cases: what if u = x (which is in S_0) and v = y (which is in S_k)? Then path is x -> ... -> y. That's exactly x then y, forbidden. Indeed, (x,y) is forbidden. (y,x) is allowed. That matches.
What if u is in S_0 but u = x itself, v in S_k; still counts. What if v = y? counts.
Thus forbidden = size of component containing x when we remove all edges on the path between x and y (i.e., the part that is "on the x side") times size of component containing y (the y side). But careful: S_0 includes x and all nodes whose unique path to y goes through x? Actually, after removing all edges of P, S_0 is exactly the component that contains x. That consists of x and all nodes that are not on the path and are connected to x via branches not using the path edges. Similarly S_k contains y and its branches.
But is there any possibility that u and v are both in S_0 and the path includes both x and y? No, we argued no. Similarly both in S_k no. So indeed all forbidden pairs are exactly those where u ∈ S_0 and v ∈ S_k.
Thus answer = total ordered pairs n*(n-1) - |S_0| * |S_k|.
But wait, is there any nuance about the path possibly including x and y even if one of them is not on the endpoints? What if u is in S_i for some i not 0,k, and v is in S_j, but the path might still include x and y if the branch for S_i includes x? No, because S_i is defined as the component after removing all P edges; that means nodes in S_i are connected to P only through pi. So from any node in S_i, to reach any node outside S_i, you must go through pi. Therefore, the path between u in S_i and v in S_j will consist of: u -> pi (within S_i), then along P from pi to pj, then pj -> v. Thus it includes only the segment of P from pi to pj. To include both p0 and pk, we need pi = p0 and pj = pk (or vice versa). So indeed only endpoints.
Thus answer seems straightforward: compute sizes of the two components when we cut the path between x and y (i.e., remove all edges on the unique path, then the components containing x and y). Multiply them, subtract from total.
But careful: The components S_0 and S_k are defined after removing all edges of the x-y path. However, note that there are also nodes on the path itself that are not x or y (the intermediate nodes p1,...,p_{k-1}). They belong to their own components S_i. But we are not counting them. So S_0 is exactly the set of nodes that are on the x side, meaning that if we cut all edges on the path, the component containing x (including x) is S_0. Similarly for y. That component includes x and all nodes that are in subtrees attached to x that do not lie towards y. But note that x might have a branch that includes a node that is actually on the path? No, by definition, the path edges are removed, so the branches are those not using the path edges. So S_0 is all nodes for which the unique path to y goes through x first? Actually, the path from any node to y is unique. If a node's path to y passes through x, then it belongs to S_0? Let's think: For any node w, consider the unique path from w to y. If this path includes x, then w is in the component of x when we cut the edge after x? But we removed all path edges, so w's connection to x might be via branches. Actually, we can think alternatively: For each node, consider the nearest node on the x-y path. That defines the component. The set S_0 consists of nodes whose nearest node on the path is x. That's equivalent to: nodes such that the path from that node to y goes through x, but also does not go through any other path node before x? Actually, the nearest node on the path is x if and only if the path from the node to x does not intersect the path x-y except at x. Which is equivalent to: the node is in the subtree "attached" to x not containing y. That's exactly what we want.
So we can compute |S_0| and |S_k| by performing a DFS from x, but avoiding going towards y? Or more systematically: Find the sizes of the components when we cut the edge on the path from x to y that is adjacent to x? Wait, we need to cut all path edges, but the sizes of S_0 and S_k are the same as if we cut just the first edge (x-p1) and compute component containing x, but careful: Cutting just the first edge yields component A = S_0, and component B = union of all other S_i (including p1,...,pk, and their branches). However, within B, there are nodes that are attached to intermediate nodes, and also the component containing y is not exactly S_k because B includes S_k and others. So if we only cut the first edge, the size of the component containing x is |S_0|, which is correct. But to get |S_k| we could cut the last edge (p_{k-1}-y) and compute the component containing y, which would be S_k. So we could compute both sizes by cutting the appropriate edges.
But we have to be careful: The sizes of S_0 and S_k can be computed without knowing the entire path? Perhaps we can compute using DFS: find the neighbor of x that lies on the path to y; if we remove that neighbor (or edge), the size of the component containing x (excluding that neighbor) is |S_0|. Similarly, find the neighbor of y on the path to x, remove that edge, the component containing y is |S_k|. However, is it true that |S_0| equals the size of the subtree of x when we root the tree at y? Or when we consider the tree rooted at x, but it's messy.
We can compute as follows: Perform a DFS from x to find y, record the parent array to know the path. Then we can compute component sizes via another DFS that excludes the path edges? Or simply: After identifying the path, we can compute for each node on the path, the size of its branch (including the node itself) but note that these branches overlap? Actually, if we consider the tree and we remove the edges of the path, each node on the path becomes a root of its own component. The size of component for node pi is: the total number of nodes in the tree that are closer to pi than any other pj? Or more concretely, it's the size of the subtree when we cut all path edges. We can compute these sizes by doing a DFS from each path node but avoiding crossing path edges. A simpler method: Since we only need sizes of the components containing x and y (S_0 and S_k), we can compute them by doing a DFS from x, but not going towards y (i.e., block the edge on the path from x to y). Similarly, from y, block the edge towards x.
Thus, algorithm:
- Read n, x, y.
- Build adjacency list.
- Find the next node from x towards y (i.e., the neighbor of x that lies on the path to y). This can be done by performing a DFS/BFS from x to find y, and record parent for each node. Then we can get the path. However, note that n up to 3e5, DFS is fine.
- After we know the neighbor of x on the path to y (call next_x), and similarly neighbor of y on the path to x (call prev_y). Actually we can get the full path. But for computing sizes, we need to know which edge to block. For S_0: the component containing x when we remove the edge (x, next_x). So we can run a DFS from x that does not traverse the edge to next_x, and count the number of nodes visited. That count is |S_0|. Similarly, for S_k: run a DFS from y that does not traverse the edge to its neighbor on the path to x (i.e., the node before y on the path; call prev_y). Count visited nodes, that's |S_k|.
But careful: what if x and y are adjacent? Then next_x = y, and prev_y = x. Then the blocked edge for x is (x,y). Then DFS from x excluding that edge will visit all nodes in the component containing x not including any nodes that require crossing to y. That's exactly S_0. Similarly DFS from y excluding edge (y,x) gives S_k. That works.
Thus answer = n*(n-1) - size_x * size_y.
But we must ensure that the pairs counted as forbidden are exactly those with u in S_0 and v in S_k. Let's verify with examples.
Example 1: n=3, edges: 1-2, 2-3, x=1, y=3. Path: 1-2-3. S_0: component of 1 after removing edges (1-2) and (2-3)? Actually we remove both path edges, S_0 = {1} (since 1 has no other branches). S_3 = {3}. So sizes: 1 and 1. Then answer = 32 - 11 = 6 - 1 = 5. Matches output.
Example 2: n=3, edges: 1-2, 1-3, x=1, y=3. Path: 1-3 (direct). S_0: component of 1 after removing edge (1,3): nodes reachable from 1 without using edge to 3. That includes 1 and 2, so size 2. S_3: component of 3 after removing edge (3,1): only {3}, size 1. Answer = 6 - 2*1 = 4. Matches output.
Another test: n=4, chain 1-2-3-4, x=2, y=3. Path: 2-3. S_0: component of 2 after removing edge (2,3). That includes nodes reachable from 2 without using edge to 3: 2 and 1, size 2. S_3: component of 3 after removing edge (3,2): includes 3 and 4, size 2. Answer = 43 - 22 = 12 - 4 = 8. Let's manually compute allowed pairs? Total ordered pairs 12. Forbidden pairs: those where u in {1,2} and v in {3,4} and path goes from u to v passes through 2 then 3 => x=2 before y=3. So forbidden = 2*2 = 4. Allowed = 8. Also check pair (2,3) is forbidden? u=2 (S_0), v=3 (S_3) => path 2->3 includes x=2 then y=3, forbidden. (3,2) allowed. (1,4) path 1-2-3-4 includes 2 then 3, forbidden. (4,1) allowed. So 4 forbidden, correct.
What about case where x and y are not directly connected and there are intermediate nodes on path. Does the definition hold? Consider a tree: 1-2-3-4-5, x=2, y=4. Path: 2-3-4. Remove edges (2,3) and (3,4). S_0: component containing 2: nodes {1,2}? Actually 2 connects to 1 and 3. Removing (2,3) leaves 2 connected to 1, so S_0 = {1,2}. S_4: component containing 4: after removing (3,4) and (4,5?) Wait, path edges are (2,3) and (3,4). When we remove both, node 3 becomes isolated? Actually we remove only the edges on the path: (2,3) and (3,4). The component containing 4 includes 4 and 5 (since 4-5 edge exists) and maybe other branches from 4. Also note that node 3 is not in S_4; node 3 is in its own component S_3 (size maybe 1 if no branches). So S_4 = {4,5}. Then sizes: 2 and 2. Answer = 54 - 22 = 20-4=16. Let's verify manually? Total 20. Forbidden: u in {1,2}, v in {4,5}. That's 2*2=4. Also what about u in {1,2} and v = 3? Path from 1 to 3: 1-2-3 includes x=2, but does it include y=4? No, because y=4 is not on path. So not forbidden. Similarly u=3 and v in {4,5} path includes 3-4 includes y=4 but does it include x=2? No (unless u=3 and v=2 includes both? Let's check: (3,2) path 3-2 includes both 2 and 4? Actually 2 is x, 4 is y, path 3-2 does not include 4. So not both). So only cross pairs between S_0 and S_4 are forbidden. So 4 forbidden. But wait, what about (2,3) includes x=2, but does it include y=4? No. So not forbidden. So 4 forbidden. Answer 16. Good.
Now consider more complex tree: x and y with branches. The reasoning seems sound.
But is there any scenario where a node is in S_0 but its path to y doesn't go through x? Actually, by definition of S_0 as component after removing path edges, any node in S_0 can reach y only by first going to x then along path. Because to leave S_0, the only edges connecting to outside are the path edges (specifically the edge from x to p1). Since we removed those edges, S_0 is isolated. So in the original tree, the only way from a node in S_0 to any node not in S_0 is through x and then the edge (x, p1). So indeed, the path from any u in S_0 to y must go through x and then along the path. So it will encounter x before y. So that matches.
Thus answer = n*(n-1) - sz_x * sz_y.
But wait: Are we sure that no other pairs are forbidden? Could there be a scenario where both x and y are on the path but u not in S_0 and v not in S_k? As argued, for both to be on the path, one must be in S_0 and other in S_k. So no.
Thus solution seems trivial. But I recall similar Codeforces problem: "Kuro and walking routes" maybe? The answer is indeed n*(n-1) - (size of subtree of x when tree rooted at y without y's direction) times (size of subtree of y when tree rooted at x). Something like that. Actually many solutions to a Codeforces problem 979C? There is problem "Kuro and Walking Routes" (maybe Codeforces Round #482 (Div. 2) C). I recall the solution is exactly n*(n-1) - sz[x]*sz[y], where sz[x] is the size of the component of x when the edge between x and y is removed? But wait, in that problem, there is a similar condition: "Kuro cannot walk through a pair if the path from u to v goes through x and then y." The solution indeed is total pairs minus product of sizes of two parts after removing the edge on the path? Actually I recall a known problem: "Kuro and Walking Route" (Codeforces 979C). I think the solution is: find the number of nodes in the subtree of x that does not contain y, and the number of nodes in the subtree of y that does not contain x. Multiply and subtract from total. That matches our S_0 and S_k.
But careful: In some variations, the path might be considered if x and y appear in order. Some solutions count forbidden as size_x * size_y, where size_x is the size of the component containing x after removing the edge on the path from x to y (i.e., the edge that connects the two sides). However, is that edge exactly the first edge? In a tree, if we only remove the edge that directly connects the two components containing x and y (i.e., the edge on the path that is adjacent to x? But if there are intermediate nodes, the edge we remove is not directly between x and y but between x and its neighbor on the path. But after removal, the component containing x is exactly S_0, and the component containing y is NOT S_k but the union of all other components, which includes intermediate nodes and their branches. That product would be larger, thus subtracting more, giving wrong answer. However, many solutions for Codeforces 979C indeed do: DFS to find the neighbor of x that is on the path to y, then compute size of subtree of x when that neighbor is considered parent, and similarly for y. But they compute sz_x as the number of nodes in the subtree of x when the tree is rooted at x? Wait, I recall the typical solution: First, find the node on the path from x to y that is adjacent to x (call it nx). Then compute the size of the component of x when the edge to nx is removed. That is the number of nodes that are in x's side. Then find the node adjacent to y on path to x (ny). Compute size of component of y when edge to ny is removed. Multiply and subtract. This is exactly what we derived: size of S_0 and size of S_k. But note that in case there are intermediate nodes, nx is the neighbor of x on the path to y; ny is the neighbor of y on the path to x. Removing those edges gives components exactly S_0 and S_k. Because S_0 is the component containing x when the edge (x, nx) is cut. S_k is the component containing y when the edge (y, ny) is cut. However, careful: In a path with intermediate nodes, the neighbor of y on the path to x is the node before y, call p_{k-1}. Removing edge (y, p_{k-1}) yields component containing y, which includes y and all branches attached to y not using that edge. But does it also include any nodes attached to intermediate nodes? No, because those are attached to p_{k-1} and are on the other side of the edge. So that component is exactly S_k. Similarly for x. So indeed, we only need to cut the immediate edge from x towards y and from y towards x. The intermediate nodes and their branches belong to neither S_0 nor S_k. So product size_x * size_y is correct.
Thus answer: total ordered pairs minus product.
Implementation steps:
- Build adjacency list.
- Perform a DFS from x to find y, recording parent array. This will give the path from x to y. But we need specifically the neighbor of x on that path (let's call next_x) and neighbor of y (prev_y). Alternatively, we can find the path by BFS/DFS and then read the second node (if exists) and second-last node. Since we only need next_x and prev_y, we can do: run DFS from x to find y, with parent tracking. Then from y, walk back using parent until we reach x. That yields the sequence. Then next_x is the node after x along this path; prev_y is the node before y. Then compute size_x: perform DFS (or BFS) starting from x, but disallow traversing the edge to next_x. Count visited nodes. Similarly size_y: DFS from y, disallow traversing the edge to prev_y. Multiply. Answer = n*(n-1) - size_x * size_y.
Edge cases:
-
x and y are adjacent: then next_x = y, prev_y = x. DFS from x excluding edge to y yields component size_x (which includes x and all nodes except those reachable only via y? Actually it's the component containing x when edge (x,y) removed). DFS from y excluding edge to x yields component size_y. That product might be less than n, but that's fine.
-
n=1? Not possible because x != y and n >=? Since x != y, n at least 2. So fine.
Complexities: O(n). Need to handle recursion depth? n up to 300k, so recursion might cause stack overflow in Python if not careful. Use iterative DFS or set recursion limit high and hope? Python recursion limit default 1000, need to increase. But using sys.setrecursionlimit(1e6) is fine but still risk of recursion depth for deep tree (could be 300k). Usually Python recursion can handle 300k depth? It might exceed stack memory. Better to use iterative BFS/DFS with stack.
We'll implement:
- adjacency list: list of lists.
- parent = [0]* (n+1)
- visited = [False]*(n+1)
- Use stack for DFS from x to find y. Since we need parent, we can do a stack with (node, par). While stack, if node == y, break. But we need to reconstruct path. We can store parent for each node during DFS. After DFS, we have parent array. Then we can reconstruct path by following parent from y back to x. But we must be careful: The DFS may not set parent for x (since it's root). We'll set parent[x] = 0.
Then we get the path list: start from y, while node != x: push node, node = parent[node]; then finally add x. Then reverse to get from x to y. Then next_x = path[1] (if path length >=2), prev_y = path[-2] (if length>=2). Since x != y, path length >=2 (since they are distinct, at least one edge). So fine.
Now compute size_x:
- Do DFS from x, but avoid going to next_x. Use stack, visited_x array or reuse a global visited? Since we only need count from x, we can do a DFS that doesn't cross that edge. Implementation: stack = [x]; visited = set or boolean array. While stack: node = pop; if not visited: visited[node]=True; for neighbor in adj[node]: if neighbor == next_x and node == x? Actually, we need to block the edge (x, next_x) regardless of direction. So if we are at x, we skip neighbor next_x. But also if we are at next_x, we skip x? But since we start from x, we will never go to next_x because we skip that neighbor. However, what if there are other ways to reach next_x from x? No, only direct edge. So by skipping that edge from x side, we will never visit next_x. So we don't need to worry about blocking the other direction because we never reach next_x. So simply in the DFS from x, when at node x, do not traverse the edge to next_x. But what if the tree has other connections? That's it.
But careful: What if x and next_x are not directly connected? next_x is neighbor on the path, so they are directly connected. So it's fine.
But what if we later visit a node that is neighbor to next_x via some other path? No, tree has no cycles; so the only path from x to any node in the component of next_x is through that edge. So by skipping that edge, we never enter that component.
Thus size_x = number of nodes visited in DFS from x with that edge blocked.
Similarly size_y: start DFS from y, skip neighbor prev_y. That yields component size of y.
Then answer = n*(n-1) - size_x * size_y.
But verify with more complex cases: Suppose there are nodes attached to intermediate nodes that are reachable from x via a path that doesn't go through next_x? No, because to get to those intermediate nodes, you must go through next_x, since next_x is the first node on the path from x to y. So they are in the other component.
Thus correct.
Now, is there any nuance about counting ordered pairs? Our total ordered pairs = n*(n-1). Forbidden = size_x * size_y. Are we sure that all such ordered pairs are indeed those where u in S_0 and v in S_k? Yes. But is there any pair where u is in S_0 and v is in S_0? That wouldn't be forbidden because path doesn't contain both. So not counted. Similarly u in S_k, v in S_k not forbidden. u in S_0 and v in S_k forbidden. u in S_k and v in S_0 allowed.
Thus answer.
But wait: What about pairs where u = x and v = something in S_k? That's included in size_x * size_y, since x ∈ S_0, v ∈ S_k. Similarly u = y, v = something in S_0 is allowed, not counted. So fine.
Now we must confirm with some additional tests.
Test: n=5, tree: star: center 1 connected to 2,3,4,5. Let x=2, y=3. Path from 2 to 3 is 2-1-3. Remove edges (2,1) and (1,3)? Actually path edges: (2,1) and (1,3). S_0: component of 2 after removing edge (2,1) is {2}, size 1. S_k: component of 3 after removing edge (3,1) is {3}, size 1. Answer = 20 - 1 = 19. Let's manually compute forbidden pairs: Those where u in S_0 (only node 2) and v in S_k (only node 3) => (2,3) forbidden. Also (2,? ) any other? (2,1) path 2-1 includes x=2, but y=3? No. (2,4) path 2-1-4 includes x=2? Yes, but does it include y=3? No. So only (2,3) is forbidden. (3,2) allowed. Also (1,?) paths: (1,2) includes x? Actually path 1-2 includes x=2? But order: from 1 to 2, does it go through x? x=2 is at the end. Does it go through x then y? It goes through x (at end) but not y. So not both. (1,3) includes y, not x. (1,4) includes neither. So forbidden count = 1. So answer 19. Works.
Test: same star, x=1, y=2. Path: 1-2. S_0: component of 1 after removing edge (1,2): nodes {1,3,4,5} size 4. S_k: component of 2 after removing edge (2,1): nodes {2} size 1. Forbidden = 4*1 = 4. Total ordered pairs = 20. Allowed = 16. Let's manually check: Forbidden pairs: u in S_0 = {1,3,4,5} and v in S_k = {2}. That's 4 pairs: (1,2), (3,2), (4,2), (5,2). Are these forbidden? Check (1,2): path 1-2: starts at x=1, then directly to y=2 => x then y, forbidden. (3,2): path 3-1-2: from 3, goes to 1 (x), then to 2 (y) => x then y, forbidden. Similarly (4,2) and (5,2) same. Other pairs: (2,1) allowed? (2,1) path 2-1: start at y then x, allowed. So indeed 4 forbidden. Good.
Now consider a case where the path between x and y has intermediate nodes with branches. Example: n=7, tree: x=1, y=4. Edges: 1-2, 2-3, 3-4, also 2-5, 3-6, 4-7. So path: 1-2-3-4. S_0: component of 1 after removing edge (1,2) = {1} (since 1 only connects to 2). size 1. S_4: component of 4 after removing edge (4,3) = includes 4 and 7, size 2. Forbidden = 12=2. Total pairs = 76=42, allowed=40. Let's check manually: Forbidden pairs are u in {1} and v in {4,7}. That is (1,4) and (1,7). Check (1,4): path 1-2-3-4 includes 1 then 4, forbidden. (1,7): path 1-2-3-4-7 includes 1 then 4 (y) before 7, but we need to check if both x and y appear: yes 1 (x) and 4 (y) both, order x then y => forbidden. (7,1): path 7-4-3-2-1 includes y first then x, allowed. So only two forbidden. Are there any other? What about (5,4)? u=5 (attached to 2), v=4. Path 5-2-3-4 includes nodes: 5,2,3,4. x=1 is not on path, so not both => allowed. (5,7): path 5-2-3-4-7 includes? 1 is not on path, so no x. Not forbidden. (6,4) includes? 6-3-4, includes y=4, but x=1 not included. So allowed. (2,4) includes? 2-3-4 includes y=4, but x=1 not included => allowed. (2,1) includes x, but y not, allowed. So indeed only two. Good.
Thus solution is correct.
Now we must think about implementation details, particularly computing size_x and size_y without recursion depth issues.
We can compute sizes via iterative DFS using stack:
def component_size(start, blocked_neighbor): visited = [False] * (n+1) maybe we can reuse a global visited for each call? But n up to 300k, we can allocate boolean list each time; two calls, okay. stack = [start] visited[start] = True size = 0 while stack: node = stack.pop() size += 1 for nb in adj[node]: if not visited[nb]: # block the edge if node == start and nb == blocked_neighbor if node == start and nb == blocked_neighbor: continue # Also, if node == blocked_neighbor and nb == start? Not needed because start won't be blocked_neighbor and we never go to blocked_neighbor because we never traverse that edge from start. But what if the blocked_neighbor appears later from other nodes? Since we never go to blocked_neighbor, it's fine. visited[nb] = True stack.append(nb) return size
But note: If start = x, blocked_neighbor = next_x. But what if next_x can be reached via some other path? No, tree no cycles. So fine.
However, we must ensure that for the DFS from y, we block the edge to prev_y. That's similar.
But we need to compute next_x and prev_y from the path.
Simpler: after obtaining the path list from x to y, next_x = path[1], prev_y = path[-2].
Now compute size_x = dfs_blocked(x, next_x); size_y = dfs_blocked(y, prev_y). Then answer = n*(n-1) - size_x * size_y.
But is there any scenario where x and y are not directly connected and the blocked neighbor for y is not unique? Actually, the neighbor of y on the path to x is unique. So fine.
Now, we must consider memory and time: adjacency list with n up to 3e5, edges n-1. DFS from x to find y O(n). Then two DFS for sizes O(n). Total O(n). Use iterative to avoid recursion.
Potential pitfalls: The initial DFS to find parent might also be done iteratively to avoid recursion. We'll use stack or BFS.
Let's design:
-
Input n, x, y.
-
Build adj list (1-indexed).
-
If n==? proceed.
-
Perform BFS/DFS from x to find y, storing parent.
Option: Use BFS queue from collections.deque.
Pseudocode:
parent = [0]*(n+1) stack = [x] parent[x] = -1 (or 0) found = False while stack and not found: node = stack.pop() for nb in adj[node]: if nb != parent[node]: parent[nb] = node if nb == y: found = True break stack.append(nb)
But careful: DFS with stack might not guarantee we break early? We can break when we find y, but we need to ensure the parent chain is correct. If we break immediately upon finding y, we might not have visited all nodes, but that's fine. The parent chain from y to x will be valid because we set parent when we first encounter each node. Since we use DFS, the first time we encounter y, we set its parent. That's fine.
But we must ensure we don't push neighbors after breaking? We can implement while loop with a flag.
Alternatively, use BFS: queue, break when we dequeue y.
Better: Use a simple stack (iterative DFS) with explicit break:
stack = [x] parent[x] = -1 visited = [False]*(n+1) visited[x]=True while stack: node = stack.pop() if node == y: break for nb in adj[node]: if not visited[nb]: visited[nb]=True parent[nb]=node stack.append(nb)
But careful: This will break when we pop y, but we might have already pushed other nodes; that's fine. The parent chain is set.
Then reconstruct path: path = [] cur = y while cur != -1: # if parent[x] = -1 path.append(cur) cur = parent[cur] Then path = path[::-1] # now from x to y
Now next_x = path[1] (if len(path)>=2) else? but x != y so len >=2. prev_y = path[-2]
Now compute size_x:
size_x = component_size(x, next_x)
Function component_size(start, blocked): visited = [False]*(n+1) # we could reuse a single visited array and reinitialize but cost O(n) to reset. We can just allocate a new boolean list each time; 2 times O(n) memory okay (two arrays of size n+1). But we could also use a global array with timestamp technique to avoid allocation, but not necessary given n=3e5, boolean list of 300k is about 300k bytes ~0.3 MB, two such ~0.6 MB, fine. stack = [start] visited[start] = True count = 0 while stack: node = stack.pop() count += 1 for nb in adj[node]: if not visited[nb]: if node == start and nb == blocked: continue visited[nb] = True stack.append(nb) return count
Similarly for size_y with start=y, blocked=prev_y.
Potential issue: For the DFS from y, we block the edge to prev_y. But what if y is adjacent to x? Then prev_y = x. In that case, blocking (y, prev_y) means not traversing edge to x from y. That will correctly count component of y without x.
Thus answer = n*(n-1) - size_x * size_y.
We should use 64-bit integer (Python int unlimited). Output as integer.
Now double-check that we didn't miss any forbidden pairs where both x and y are on the path but u is not in S_0 or v not in S_k. For example, consider if u is in S_0 and v is also in S_0? Then path does not include y. So not both. So no.
What if u is on the path itself, say u = p_i for some i between 0 and k, and v = p_j, and the path includes both x and y? For i=0, j=k -> that is u in S_0 (since p0 = x is in S_0? Actually, p0 is x, which is part of S_0). v = pk = y, part of S_k. So that's already counted. For i=0, j=some intermediate, missing y. So not both. For i intermediate, j=k, missing x. So not both. For i,j both intermediate, missing both endpoints. So indeed only the cross between S_0 and S_k yields both.
What about u in S_0 and v is some node that is on the path but not an endpoint? For v = p_i (i>0). The path from u (in S_0) to p_i goes: u -> ... -> x -> p1 -> ... -> p_i. Does it include y? Only if i = k. So only when i=k. So again only when v = y.
Thus our counting stands.
Now consider if u = x and v = some node in S_k, that's counted. Similarly u in S_0 but not x, v in S_k.
Thus answer is correct.
Now, check constraints: n up to 3e5, recursion not used, O(n) time, memory O(n). Good.
But wait, one more nuance: The problem says "he will avoid any pair of towns (u, v) if on the path from u to v, he reaches Beetopia after he reached Flowrisa". This means if the path contains both, and x appears before y. So yes.
Now, test with sample inputs, matches.
Now let's test with a more complicated tree: n=6, edges: 1-2, 2-3, 3-4, 4-5, 5-6 (a chain). x=2, y=5. Path: 2-3-4-5. S_0: component of 2 after removing edge (2,3): includes nodes 1 and 2, size 2. S_k: component of 5 after removing edge (5,4): includes nodes 5 and 6, size 2. Forbidden = 22=4. Total pairs = 65=30. Allowed=26. Let's manually compute: Forbidden: u in {1,2} and v in {5,6} -> (1,5),(1,6),(2,5),(2,6). Check (1,5): path 1-2-3-4-5 includes 2 then 5, forbidden. (1,6): 1-2-3-4-5-6 includes 2 then 5, forbidden. (2,5): 2-3-4-5 includes 2 then 5, forbidden. (2,6): 2-3-4-5-6 includes 2 then 5, forbidden. (5,1): allowed, (6,1) allowed, etc. So 4 forbidden, correct.
Now test scenario where there is a branch attached to intermediate node that is large: n=10, path 1-2-3-4, with node 2 attached to many nodes. x=1, y=4. S_0: component of 1 after removing edge (1,2) = {1}? If 1 only connects to 2, size=1. S_4: component of 4 after removing edge (4,3) = {4} plus any branches from 4. Suppose 4 has branches, so size maybe >1. Forbidden = 1 * size_y. Check if any other forbidden? Could there be a pair where u is in branch attached to 2 (which is not in S_0) and v in S_4? That's u in S_2? Actually branch attached to 2 is part of component S_2 (if we define S_i as per path nodes). Since u not in S_0 but in S_2, v in S_4, path from u to v goes: u -> 2 -> 3 -> 4 -> ... to v. That includes x? x=1 is not on the path because path from u to v goes from u to 2 (which is not x), then 3, then 4, then v. So x=1 is not on the path. So not forbidden. So indeed only S_0 and S_4 cross.
Thus answer stands.
Now, I recall a known Codeforces problem: 979C - Kuro and Walking Route. Indeed the solution is exactly that. I can confirm from memory: The answer is n*(n-1) - sub_x * sub_y, where sub_x is the size of the subtree of x when the tree is considered with parent as the neighbor towards y? Yes.
Thus implement.
Now, consider the possibility that the path from x to y is just one edge. Then next_x = y, prev_y = x. The component sizes are as described.
Now, verify with second sample: we did.
Now test with n=2: only two nodes, edge between them, x=1, y=2. Then total pairs = 2*1=2. S_0: component of 1 after removing edge to 2: only {1}, size 1. S_2: component of 2 after removing edge to 1: only {2}, size 1. Forbidden =1. Answer=1. Which ordered pair is allowed? Forbidden: (1,2) because x then y. Allowed: (2,1). So answer 1. That matches intuition.
Thus implementation seems fine.
Now, regarding DFS for sizes: We'll use iterative stack. However, we can also compute sizes without extra DFS by using subtree sizes from a root, but easier to just DFS.
But we need to be careful about not traversing the blocked edge: In the component size function, we block only when current node is start and neighbor is blocked. However, what if the blocked neighbor is not directly adjacent to start? It is directly adjacent because we set blocked as the immediate neighbor on the path. So it's fine. But we must also block the reverse direction? Since we start from start and never cross that edge, we will never reach the blocked neighbor, so reverse direction never occurs. So okay.
Edge case: If the tree is deep, stack size might become large but Python list as stack can handle 300k elements, okay.
Now, test with n=300k linear chain, x=1, y=n. Then the DFS from x to find y: we can use BFS/DFS but it's linear, fine. The component size for x will be 1 (since only node 1 if we block edge to node2). That DFS will just visit node1, trivial. For y, component size is 1 (since block edge to node n-1). So forbidden =1. Answer = n*(n-1)-1. But is that correct? Let's think: In a chain 1-2-3-...-n, x=1, y=n. Forbidden pairs are those where u in S_0={1} and v in S_n={n}. So only (1,n) is forbidden. Indeed, all other pairs either don't include both endpoints or include them in reverse order? For pair (2,n): path 2-3-...-n includes y=n but not x=1, so allowed. (1,2): includes x but not y, allowed. (n,1): includes both but order y then x, allowed. So only one forbidden. So answer = n*(n-1)-1, which for n=300k is large, correct.
Now test x and y in the middle of chain: say x=100, y=200. Then S_0 includes nodes 1..100? Actually, we need to compute component of x when we cut the edge from x to x+1 (the neighbor towards y). Since it's a chain, the component containing x includes all nodes from 1 to x. Because from x, you can go to x-1, x-2, ..., 1 via the chain, but not towards y because that edge is blocked. So size_x = x. Similarly, component of y when we cut edge to y-1 includes nodes from y to n. So size_y = n - y + 1. Forbidden = x * (n - y + 1). Let's test with n=10, x=3, y=7 (chain). S_0: nodes 1,2,3? Actually, component of 3 after cutting edge (3,4) includes nodes 1,2,3? Since from 3 you can go to 2 and 1. So size 3. S_7: after cutting edge (7,6) includes nodes 7,8,9,10 => size 4. Forbidden = 12. Total pairs=90, allowed=78. Let's manually count? Probably correct.
Now, we must be absolutely sure that there is no other forbidden scenario. For instance, what if the path from u to v includes both x and y but in the order x then y, but u and v are such that u is not in S_0? Could that happen? Suppose u is in S_i for i>0, and v is in S_k. The path from u to v would be: u -> p_i -> ... -> p_k -> v. This includes p_i,...,p_k. For it to include x (=p0), we need i=0. So not. Similarly, if u in S_0 and v in S_i (i<k), then path includes p0..p_i, missing y if i<k. So no.
Thus it's settled.
Now, we must also consider that the problem statement says "he reaches Beetopia after he reached Flowrisa". Does "reaches" mean he passes through those towns? If he starts at Flowrisa, he "reaches" Flowrisa at start? Typically yes, if u = x, then he starts at x, so he reaches x at the beginning. So that counts as reaching Flowrisa. Similarly, if v = y, he reaches y at the end. So all good.
Now, implement.
Potential pitfalls: The DFS to find path might be done without visited array, using parent to avoid revisiting parent. In iterative DFS, we can just use parent to avoid going back.
Simplify: Use BFS from x to find y, which naturally gives shortest path (since tree). BFS with queue.
from collections import deque
queue = deque([x]) parent = [0]*(n+1) parent[x] = -1 while queue: node = queue.popleft() if node == y: break for nb in adj[node]: if nb != parent[node]: parent[nb] = node queue.append(nb)
This BFS will find y and set parents correctly. Since tree, BFS is fine and O(n). Then reconstruct path.
Now, compute sizes:
def get_size(start, forbid): # forbid is the neighbor not to go to from start stack = [start] visited = [False]*(n+1) visited[start] = True size = 0 while stack: node = stack.pop() size += 1 for nb in adj[node]: if not visited[nb]: if node == start and nb == forbid: continue visited[nb] = True stack.append(nb) return size
But note: In get_size for y, we forbid prev_y. But what if y has multiple neighbors? We only forbid the specific neighbor that lies on the path to x. That's correct.
Now, answer = n*(n-1) - size_x * size_y.
But wait: Are we sure that size_x is exactly |S_0|? Let's double-check with a scenario where x has multiple branches, including one that leads to y via some other path? But tree is acyclic, so only one simple path to y. So yes.
Now, consider a case where the path between x and y includes intermediate nodes that have large branches. For size_x we only count nodes reachable from x without going through next_x. That includes x and all nodes in subtrees attached to x except the one towards y. That's exactly S_0.
Now, is it possible that some nodes that are in S_0 are reachable from x only via next_x? No, because next_x is the only connection to the rest of the tree beyond the branch of x. So blocking that edge isolates S_0.
Thus correct.
Now, let's test on random small trees to be extra sure. We'll do mental checks.
Case: n=4, edges: 1-2, 2-3, 2-4. x=3, y=4. Path: 3-2-4. S_0: component of 3 after removing edge (3,2) => {3} size 1. S_4: component of 4 after removing edge (4,2) => {4} size 1. Forbidden =1. Total pairs=12, answer=11. Let's enumerate: Nodes:1,2,3,4. Forbidden pairs: u in S_0={3}, v in S_4={4} => (3,4) only. Check (3,4): path 3-2-4, includes x=3 then y=4? Actually x=3, y=4. So 3 then 4, yes forbidden. (4,3) allowed. Others all allowed? Check (1,4): path 1-2-4 includes y=4, but x=3? Not on path, so allowed. (3,1): path 3-2-1 includes x=3, but not y, allowed. (1,3): path 1-2-3 includes x=3 at end, but y=4? no. So indeed only one forbidden. So answer 11.
Now, what if we had x=2, y=4 in same tree: Path 2-4 (direct). S_0: component of 2 after removing edge (2,4): from 2, without using edge to 4, we can go to 1 and 3 => {2,1,3} size 3. S_4: component of 4 after removing edge (4,2): {4} size 1. Forbidden =3. Total=12, allowed=9. Check forbidden: u in {1,2,3} and v=4: (1,4),(2,4),(3,4). (1,4) path 1-2-4 includes x=2 then y=4, forbidden. (2,4) path 2-4, forbidden. (3,4) path 3-2-4, forbidden. Others allowed. (4,1) allowed, etc. So 9 allowed. Good.
Now, consider a more complex case where x and y are not endpoints of the tree, but one of them is in a branch. Our method still works.
Now, I think solution is correct.
Now, we must consider large n and recursion. We'll implement iterative.
Potential improvement: Instead of doing two DFS for sizes, we could compute sizes by doing a DFS from x to compute subtree sizes, but with blocked neighbor. But it's fine.
Now, we should also consider the possibility that we might not need to compute full path; we can find the neighbor of x on the path to y by doing a DFS from x, and when we encounter y, we can backtrack to get the immediate neighbor of x. But we need the neighbor for y as well. So path reconstruction is fine.
Alternatively, we can compute sizes directly without path reconstruction:
- Perform DFS from x to compute parent and also find y. Then from y, trace back to x to get the node before y (prev_y) and the node after x (next_x). Then do DFS from x ignoring next_x; from y ignoring prev_y. That's what we do.
Now, we need to be careful about memory: visited arrays for two DFS. But we can reuse a single array with a marker (like timestamp) to avoid multiple allocations, but not needed.
Now, time: O(n). Should pass.
Now, confirm sample input 2: We computed earlier and got 4, matches.
Now, check a random test: n=5, edges: 1-2,2-3,3-4,4-5, and x=2, y=4. Our answer: n*(n-1)=20, size_x: component of 2 after removing edge to 3? Since path: 2-3-4. Next_x = 3. From 2, without using 3, we can go to 1, so size_x=2 (nodes 1,2). size_y: component of 4 after removing edge to 3: from 4, without using 3, we can go to 5, so size_y=2 (4,5). Forbidden =4, answer=16. Let's manually enumerate all ordered pairs (1..5). Forbidden pairs: u in {1,2} and v in {4,5}: (1,4),(1,5),(2,4),(2,5). Check (3,4): not forbidden because x? path 3-4 includes y=4, but x=2 not included. (3,5): 3-4-5 includes y=4? Actually y=4 is on path but x=2 not, not both. (5,2): 5-4-3-2 includes y=4 then x=2 => allowed (since order y then x). So only 4. So answer=16.
Now, everything consistent.
Thus answer is trivial.
Now, I recall some participants in Codeforces missed the fact that only the immediate neighbor matters, and mistakenly computed size of subtree of x when tree rooted at some arbitrary root, etc. But the official solution is exactly this.
Now, ensure we output as integer.
Edge Cases:
- n=1 not possible because x != y.
- n=2 works.
- tree as star works.
- x and y could be in any order.
Thus final solution.
Now, double-check with sample 1: n=3, edges:1-2,2-3, x=1,y=3. Next_x = 2 (since path 1-2-3). size_x: from 1 block 2 -> only node 1, size=1. size_y: from 3 block 2 -> only node 3, size=1. answer=6-1=5. matches.
Sample 2: n=3, edges:1-2,1-3, x=1,y=3. Next_x = 3, size_x: from 1 block 3 -> can go to 2, so nodes 1,2? Wait, careful: start=1, blocked=3. From 1, neighbors: 2 and 3. Block 3, so only traverse to 2. Then from 2, neighbors: 1 (already visited). So visited nodes: 1 and 2. So size_x=2. size_y: start=3, blocked=1 (since prev_y=1). From 3, neighbors: 1 (blocked) so no other neighbors; visited:3 only. size_y=1. Answer=6-2=4. matches.
Now, ensure that when we compute size_y, we block prev_y. In this case, prev_y = 1, correct.
Now, if the tree is large, we must be careful not to cause recursion.
Now, implement.
But there is one more nuance: In the component size function, we only block when node == start and nb == forbid. However, if the start node has multiple edges, we block only that specific neighbor. But what if the start node also has another neighbor that leads to forbid via a longer path? No, tree no cycles, so if we block the direct edge, we will never reach forbid.
Now, think about if start node is y and forbid is prev_y, but what if y also has other neighbors that are not on the path? Those are fine; they are part of S_k. So we don't block them.
Now, check for correctness in a scenario where the start node has the forbid neighbor, but we might inadvertently traverse from some other node to forbid later. For example, start = x, forbid = next_x. Could we reach next_x from x via another path? No, because tree, only one path.
Thus fine.
Now, we could also compute sizes using a single DFS that computes subtree sizes for each node when the tree is rooted arbitrarily, and then determine the sizes by identifying the child of x that is on the path to y, and similarly for y. But our method is simpler.
Now, I will proceed to implement solve().
Pseudo-code:
import sys sys.setrecursionlimit(1<<25) but not needed if iterative.
def solve(): import sys input = sys.stdin.readline n, x, y = map(int, input().split()) adj = [[] for _ in range(n+1)] for _ in range(n-1): a,b = map(int, input().split()) adj[a].append(b) adj[b].append(a) # BFS from x to find y and parent from collections import deque parent = [0](n+1) q = deque([x]) parent[x] = -1 while q: u = q.popleft() if u == y: break for v in adj[u]: if v != parent[u]: parent[v] = u q.append(v) # reconstruct path from x to y path = [] cur = y while cur != -1: path.append(cur) cur = parent[cur] path.reverse() # now path[0]=x, path[-1]=y next_x = path[1] prev_y = path[-2] # function to compute component size from start without traversing blocked neighbor def comp_size(start, blocked): visited = [False](n+1) stack = [start] visited[start] = True cnt = 0 while stack: node = stack.pop() cnt += 1 for nb in adj[node]: if not visited[nb]: if node == start and nb == blocked: continue visited[nb] = True stack.append(nb) return cnt size_x = comp_size(x, next_x) size_y = comp_size(y, prev_y) ans = n*(n-1) - size_x * size_y print(ans)
if name == "main": solve()
Now, test with provided examples.
But wait: In comp_size, we only block when node == start and nb == blocked. However, what if start == x and blocked = next_x, but we might later visit a node that is adjacent to next_x from another node? That would require reaching next_x, which we cannot because we never traverse the edge from start to blocked. Since it's a tree, there is no other path to next_x from start without crossing that edge. So next_x will never be visited. So any neighbor of next_x other than start will not be visited because we never reach next_x. So it's safe.
But what if the blocked node is also reachable from start via some other route? In a tree, there is exactly one simple path between any two nodes. So if blocked is neighbor of start, the only path from start to blocked is the direct edge. So no alternative.
Thus correct.
Now, potential issue: In comp_size for y, we start at y, blocked = prev_y (neighbor towards x). Similar reasoning.
Now, complexity: BFS O(n), two DFS O(n). Memory: adj list O(n), parent O(n), visited arrays O(n) each call, but we allocate new each time, so at peak maybe 2 arrays? Actually we allocate visited inside comp_size twice, but they are sequential, not simultaneously, so maximum memory is O(n) for adjacency plus a couple of arrays of size n. So overall ~ few MB, fine.
Now, we can also compute sizes without extra visited arrays by using parent tracking and avoiding the blocked edge. But it's fine.
Now, confirm with large input.
Now, let's test with a more tricky case: Suppose x and y are such that there is a branch attached to x that includes y? That's impossible because y is distinct and tree is acyclic, so y cannot be in a branch of x if the path from x to y goes through that branch. But if x and y are adjacent, then y is neighbor of x, so the branch of x that contains y is via that edge. So when we block that edge, we exclude y and its side.
Now, consider the scenario where the tree has 300k nodes, and the path is long. BFS from x to y might go through many nodes, but that's okay.
Now, could there be a case where parent[] is not fully set for all nodes before we break? We only need the path from y to x, which is set correctly because we set parent as we traverse. When we break upon popping y from queue, we have parent[y] set. But we may not have visited all nodes, but we don't need them. The path from y back to x using parent will be correct because parent chain exists and is unique.
But caution: In BFS, we break when we pop y from queue. But we still need parent for all nodes along the path. Since we set parent when we first discover a node, and BFS ensures that the first discovery gives the shortest path (which in a tree is the unique path). So parent[y] is the node that first discovered y. That is the neighbor on the shortest path from x. Since tree has only one simple path, that's correct. So path reconstruction is fine.
Alternatively, we could use DFS to find y, but BFS is fine.
Now, one more nuance: When we BFS, we use a condition "if v != parent[u]" to avoid going back. This works because parent[u] is set. For root x, parent[x] = -1, so all neighbors are considered.
Now, we break out of while loop when u == y. But what if y is not reached? But it's a tree, so it will be reached.
Now, about the path list: We do while cur != -1: path.append(cur); cur = parent[cur]. This will include x because parent[x] = -1, so when cur becomes x, we append x, then cur = parent[x] = -1, loop stops. So path contains x,...,y. Then we reverse.
Now, next_x = path[1] and prev_y = path[-2]. Since path length >=2, safe.
Now, compute sizes.
Now, output ans.
Now, double-check that size_x and size_y are computed correctly even when the blocked neighbor is not a neighbor? For instance, if x and y are same? Not allowed. So fine.
Now, but there is a scenario: what if x and y are such that the path length is >1, but x has degree 1 (only neighbor is next_x). Then component of x after blocking next_x is just {x}. That's correct.
Now, what about y having degree 1? Similar.
Now, everything is fine.
But I recall there is a known alternative solution: answer = n*(n-1) - subSizeX * subSizeY, where subSizeX is the size of the component containing x after removing the edge on the path from x to y. That's exactly our size_x.
Thus the solution is correct.
Now, implement with reading input fast (sys.stdin.buffer). Use sys.setrecursionlimit maybe not needed.
Now, write final code.
But before finalizing, let's double-check with a more complex tree, manually compute with code logic:
Tree: n=7, edges: 1-2, 2-3, 2-4, 3-5, 3-6, 6-7. x=1, y=7. Path from 1 to 7: 1-2-3-6-7. So next_x = 2. prev_y = 6. Component of 1 after blocking 2: just {1}, size_x=1. Component of 7 after blocking 6: just {7}? Let's see: 7 is connected to 6, block 6 => only {7}, size_y=1. Forbidden=1. Total=42, answer=41. Let's see if any other pairs are forbidden? (1,7) is obviously forbidden. What about (2,7)? Path 2-3-6-7 includes y=7, but x=1 not on path, so allowed. (5,7): 5-3-6-7 includes y, not x. So only (1,7) is forbidden. So answer 41.
Now, if we change x=2, y=7: Path: 2-3-6-7. next_x = 3, component of 2 after blocking 3: from 2, we can go to 1 and 4 (since 2 is connected to 1,3,4). Block 3, so can go to 1 and 4. Also from 1 no further, from 4 none. So size_x = nodes {2,1,4} = 3. prev_y = 6, component of 7 after blocking 6: just {7}, size_y=1. Forbidden=3. Total=42, answer=39. Forbidden pairs: u in {1,2,4} and v=7: (1,7),(2,7),(4,7). Check (2,7): path 2-3-6-7 includes x=2 then y=7, forbidden. (1,7): path 1-2-3-6-7 includes 2 then 7, forbidden. (4,7): 4-2-3-6-7 includes 2 then 7, forbidden. Others allowed. (7,2) allowed. So correct.
Now, if we change x=3, y=6: Path: 3-6. next_x = 6, component of 3 after blocking 6: from 3, neighbors: 2,5,6. Block 6, so can go to 2 and 5. 2 connects to 1 and 4, and 5 is leaf. So nodes reachable: 3,2,5,1,4 = 5 nodes? Wait total n=7. Nodes: 1,2,3,4,5,6,7. So from 3, via 2 we get 1,2,4. And via 5 get 5. So {1,2,3,4,5} = 5 nodes. prev_y = 3, component of 6 after blocking 3: from 6, neighbors: 3 and 7. Block 3, so only 7 reachable. So size_y = {6,7}? Actually start at 6, block 3, then from 6 we can go to 7. So visited: 6 and 7. So size_y=2. Forbidden = 52=10. Total=42, answer=32. Let's check manually? Might be correct: Forbidden: u in {1,2,3,4,5} and v in {6,7}. That's 52=10 pairs. Verify if any of those have both x=3 and y=6 on path and order x before y? For u in S_0 (which includes 3 itself) and v in S_k (includes 6 and 7). For pair (3,6): path 3-6 includes x then y, forbidden. (3,7): path 3-6-7 includes x then y, forbidden. (2,6): path 2-3-6 includes x=3? Actually x=3, y=6. Path from 2 to 6: 2-3-6. Does it include x=3? Yes, and y=6, order 3 then 6, so forbidden. (2,7): 2-3-6-7 includes 3 then 6, forbidden. (1,6): 1-2-3-6 includes 3 then 6, forbidden. (1,7): 1-2-3-6-7 includes 3 then 6, forbidden. (4,6): 4-2-3-6 includes 3 then 6, forbidden. (4,7): similar. (5,6): 5-3-6 includes 3 then 6, forbidden. (5,7): 5-3-6-7 includes 3 then 6, forbidden. So indeed 10. So answer 32.
Now, what about pair (6,3)? allowed. Good.
Thus answer works.
Now, we should be aware of potential integer overflow? In Python no.
Now, implement.
But wait: There is another nuance: The problem statement says "Kuro will avoid any pair of towns (u, v) if on the path from u to v, he reaches Beetopia after he reached Flowrisa". Does "reaches" mean that he actually passes through the town? If he starts at Flowrisa, he is at Flowrisa at the beginning. That's reaching. If he ends at Beetopia, he reaches Beetopia at the end. So that's included.
Now, does the path need to contain both exactly? Yes.
Thus fine.
Now, we can think about alternative counting: Could there be any pair where u = x and v = something that is in S_k, but the path goes through x then later y. That's included.
Now, confirm that the product size_x * size_y is the number of ordered pairs (u,v) where u in S_0 and v in S_k. That's because ordered pairs: for each u in S_0, each v in S_k gives a distinct ordered pair. So product.
Now, we should also check that S_0 and S_k are disjoint? Since they are different components after removing path edges, they are disjoint. Their sizes sum at most n, but not necessarily n because there are intermediate components. So fine.
Now, answer = total - product.
Now, one more thought: Could there be any forbidden pair where u and v are the same? No, because u != v. So not an issue.
Now, we can go ahead.
Implementation details: Use sys.stdin.buffer for faster input.
Now, code.
But wait: The BFS we used breaks when we pop y. However, in BFS, we might push y's neighbors before we break? Actually, we check after popping u. If u == y we break. But we may have already pushed some nodes after discovering y? Actually, when we discover y, we set parent[y] from its neighbor and then we push y onto the queue. At that time, we haven't processed y yet. Later when we pop y, we break. So that's fine. The BFS loop only processes a node when popped. So we break before exploring y's neighbors, but we don't need them.
Now, reconstruct path.
Now, about comp_size: visited list of size n+1 each call. This could be heavy for large n but okay: two times 300k booleans ~ 600k bytes, fine. But Python booleans are objects? Actually list of bools uses Python objects (True/False) which are objects, but they are singletons, still list stores references, each 8 bytes on 64-bit, so 300k * 8 ~ 2.4 MB per list. Two lists would be 4.8 MB, plus adjacency list, parent, etc. Total maybe 20-30 MB, within typical limits (256 MB). So fine.
We could also use bytearray for visited to be memory efficient, but not necessary.
Alternative: Use recursion? Not advisable.
Now, code final.
Now, let's test with the given examples.
Example 1: Input: 3 1 3 1 2 2 3
Our code: n=3,x=1,y=3. adj: [1:2, 2:1,3, 3:2]. BFS from 1: queue start [1], parent[1]=-1. pop 1, neighbors 2, parent[2]=1, push 2. queue now [2]. pop 2, neighbors 1 and 3. 1 is parent, ignore; 3 not visited, parent[3]=2, push 3. queue [3]. pop 3, u==y break. path: cur=3 -> path.append(3), cur=parent[3]=2, append 2, cur=parent[2]=1, append 1, cur=parent[1]=-1 stop. path = [3,2,1], reverse => [1,2,3]. next_x=2, prev_y=2. comp_size(1,2): visited [False]*4. start=1, blocked=2. stack [1], visited[1]=True. pop 1, count=1; neighbors 2: node==start and nb==blocked => skip. So only neighbor visited? Actually also maybe other neighbors? 1 only has neighbor 2. So stack empty, count=1. size_x=1. comp_size(3,2): start=3, blocked=2. stack [3], visited[3]=True. pop 3, count=1; neighbors: 2. node==start and nb==blocked => skip. So size_y=1. ans=6-1=5. correct.
Example 2: 3 1 3 1 2 1 3
adj: 1:[2,3], 2:[1], 3:[1]. BFS from 1: queue [1], parent[1]=-1. pop 1, neighbors 2 and 3. set parent[2]=1, push 2; parent[3]=1, push 3. queue [2,3]. pop 2, neighbors 1 (parent) ignore. pop 3, u==y break (since y=3). path: cur=3 -> append 3, cur=parent[3]=1, append 1, stop. path=[3,1], reverse => [1,3]. next_x=3, prev_y=1. comp_size(1,3): start=1, blocked=3. stack [1], visited[1]=True. pop 1, count=1; neighbors 2,3. neighbor 2: not visited, and (node==start and nb==blocked? nb=2 not blocked) so visit 2, push; neighbor 3: node==start and nb==blocked => skip. Then stack [2]; pop 2, count=2; neighbors 1 visited, done. size_x=2. comp_size(3,1): start=3, blocked=1. stack [3], visited[3]=True. pop 3, count=1; neighbors: 1 is blocked and node==start, skip. So size_y=1. ans=6-2=4. correct.
Thus fine.
Now, let's think about possible pitfalls: The BFS might have a bug if we break immediately after discovering y? In our BFS we break when we pop u, not when we discover. But we might discover y earlier when exploring a node, but we still push y onto queue. Then when we pop it, we break. That's fine. But what if we want to break earlier to save time? Not needed.
Now, consider if the tree is deep, BFS queue might be large but okay.
Now, implement final code.
But hold on: There is a known alternative solution that says answer = n*(n-1) - szX * szY, where szX is the size of the component containing X when the edge on the path from X to Y is removed (the edge adjacent to X). But we used that. So fine.
Now, let's ensure we handle the case where x and y are not adjacent: next_x is the neighbor of x towards y. That neighbor might be p1. Similarly, prev_y is the neighbor of y towards x. This is fine.
Now, we need to be careful about reading input: n up to 300k, lines n-1, use sys.stdin.buffer.
Now, final code.
One more nuance: In comp_size, we set visited[nb] = True before pushing to stack. This is to avoid duplicate pushes. Good.
Now, test with large chain manually: n=300000, chain 1-2-...-n, x=1, y=n. BFS from 1 to n will traverse entire chain, O(n). Then comp_size(1,2) will just visit node 1 (size 1). comp_size(n, n-1) just visit node n (size 1). So fine.
Now, memory: adjacency list for chain: each node has up to 2 neighbors, total edges ~2n, list of lists; fine.
Now, we may also compute sizes without extra visited by using parent array but simpler to use visited.
Now, finalize.
But wait: There's a more elegant way: size_x = subtree size of x when tree is rooted at y? Actually, we could compute subtree sizes via DFS from x, but we need to block the edge.
Now, all good.
Now, let's produce final answer.
But before finishing, I'll consider if there is any scenario where the forbidden pairs are not exactly size_x * size_y because of nodes that are on the path? For instance, what if u is in S_0 and v is also in S_0? That's not forbidden. What if u is in S_k and v in S_k? Not forbidden. What if u in S_0 and v in S_k is forbidden. What about u in S_0 and v = some node that is on the path but not y? Then y not on path, so not both. So no.
Now, what about u = a node in S_0 and v = a node in some intermediate branch (S_i, i between 1 and k-1)? Then path does not include y. So no.
Thus correct.
Now, we can finalize.
Now, one more thought: The problem says "he reaches Beetopia after he reached Flowrisa". Could it be that if the path passes through Flowrisa and then later Beetopia, it's forbidden, regardless of whether he starts or ends at them. Yes. So our interpretation holds.
Thus answer.
Now, write final solution in Python.
I will include comments for clarity.
Now, check for potential improvements: Use sys.setrecursionlimit but we don't use recursion.
Now, final code:
import sys from collections import deque def solve(): data = sys.stdin.buffer.read().split() it = iter(data) n = int(next(it)) x = int(next(it)) y = int(next(it)) adj = [[] for _ in range(n+1)] for _ in range(n-1): a = int(next(it)); b = int(next(it)) adj[a].append(b) adj[b].append(a) # BFS to find path from x to y parent = [0]*(n+1) q = deque([x]) parent[x] = -1 while q: u = q.popleft() if u == y: break for v in adj[u]: if v != parent[u]: parent[v] = u q.append(v) # reconstruct path path = [] cur = y while cur != -1: path.append(cur) cur = parent[cur] path.reverse() # now path[0] = x, path[-1] = y next_x = path[1] prev_y = path[-2] # compute component size from start without traversing blocked neighbor def comp_size(start, blocked): visited = [False]*(n+1) stack = [start] visited[start] = True cnt = 0 while stack: node = stack.pop() cnt += 1 for nb in adj[node]: if not visited[nb]: if node == start and nb == blocked: continue visited[nb] = True stack.append(nb) return cnt size_x = comp_size(x, next_x) size_y = comp_size(y, prev_y) ans = n*(n-1) - size_x * size_y print(ans) if __name__ == "__main__": solve()Now, test with sample inputs.
All good.
Now, I will produce final answer. ```python import sys from collections import deque
def solve() -> None: data = sys.stdin.buffer.read().split() it = iter(data) n = int(next(it)) x = int(next(it)) y = int(next(it))
adj = [[] for _ in range(n + 1)] for _ in range(n - 1): a = int(next(it)) b = int(next(it)) adj[a].append(b) adj[b].append(a) # ---- find the unique path from x to y ---- parent = [0] * (n + 1) q = deque([x]) parent[x] = -1 while q: u = q.popleft() if u == y: break for v in adj[u]: if v != parent[u]: parent[v] = u q.append(v) # reconstruct the path (x -> ... -> y) path = [] cur = y while cur != -1: path.append(cur) cur = parent[cur] path.reverse() # now path[0] = x, path[-1] = y nxt_x = path[1] # neighbour of x on the path to y prv_y = path[-2] # neighbour of y on the path to x # ---- count nodes in the component of a start node when a given edge is blocked ---- def component_size(start: int, blocked: int) -> int: visited = [False] * (n + 1) stack = [start] visited[start] = True cnt = 0 while stack: node = stack.pop() cnt += 1 for nb in adj[node]: if not visited[nb]: # block the edge (start, blocked) only when we are at start if node == start and nb == blocked: continue visited[nb] = True stack.append(nb) return cnt size_x = component_size(x, nxt_x) # |S_x| size_y = component_size(y, prv_y) # |S_y| total_pairs = n * (n - 1) forbidden = size_x * size_y print(total_pairs - forbidden)if name == "main": solve()
-