Time limit: 2 seconds Memory limit: 256 MB Source: The first final exam of the 26th…
- User
Time limit: 2 seconds Memory limit: 256 MB Source: The first final exam of the 26th Computer Olympiad Amin has gone to Postun for vacation. One of the tourist attractions of Postun is its large and beautiful squares. The city squares are connected to each other by a number of streets.
Amin can take a taxi from Uber or Snap to move between squares in the city! Each of these two companies has covered a set of city streets, so that with the streets covered by each company alone, you can go from any square to any other square with a unique route. Also, there is no street that is covered by both Uber and Snap.
Amin wants to go around the squares of the city. He performs round-robin operations in such a way that he starts from an arbitrary square, does not cross any street more than once, and finally returns to the first square. In each move, he takes a taxi from one of the two companies and goes from one end of a street that is covered by that company to the other end of that street.
Because the cost of using Uber taxis is very high, Amin can use them at most twice, but he can use Snap taxis as many times as he wants. On the other hand, Uber taxis are far more luxurious than Snap taxis, and as a result, he intends to use twice as much as he can pay for Uber taxis. So a round trip is profitable from Amin's point of view if and only if Uber taxis are used exactly twice during it.
Amin considers two rounds as different if in one of them we cross a street that we will not cross in the other round. Can you count the number of different laps Amin can do by taking the routes covered by Uber and the routes covered by Snap?
input In the first line of input number n n is the number of Poston fields. in n
1 n−1 next line, two natural numbers in each line v s , i v s.i and u s , i u s.i It is said that it shows that the street connecting those two squares is covered by SNAP. in n
1 n−1 next line, two natural numbers in each line v u , i v u, i and u u , i u u, i It is said that it shows that the street connecting those two squares is covered by Uber. There is at most one street between both squares. With the taxis covered by each company, you can get from any square to any other square.
4 ≤ n ≤ 100
000 4≤n≤100 000 1 ≤ v s , i , u s , i ≤ n 1≤v s.i ,u s.i ≤n 1 ≤ v u , i , u u , i ≤ n 1≤v u, i ,u u, i ≤n
output On the only output line, print the number of rounds of economical rounds in your post.
Sub-issues Constraint score subproblem 1 20 n ≤ 100 n≤100 2 22 n ≤ 3
000 n≤3 000 3 58 without additional restrictions Example Sample entry 1 4 1 2 2 3 3 4 1 3 1 4 2 4 Plain text Sample output 1 3 Plain text Sample input 2 7 1 2 1 3 2 4 2 5 3 6 3 7 1 4 4 5 1 7 7 6 6 2 2 3 Plain text Sample output 2 12
- Assistant
To solve this problem, we need to compute the number of different cycles that meet Amin's criteria.
First, we need to understand the key observations:
-
Uber Edges as Fundamental Cycles: Each Uber edge, when added to the Snap tree, forms a unique fundamental cycle in the union graph. The fundamental cycle consists of the Uber edge and the unique path between its endpoints in the Snap tree.
-
Cycle Overlaps: If two Uber edges share any nodes or edges in their fundamental cycles (i.e., their paths in the Snap tree overlap), then their cycles cannot be combined to form a valid cycle using exactly two Uber edges without repeating an edge.
-
Counting Valid Pairs of Uber Edges: We need to count the number of pairs of Uber edges whose fundamental cycles are edge-disjoint in the Snap tree (i.e., their paths in the Snap tree do not overlap). Each such pair corresponds to a unique valid cycle Amin can take.
To efficiently count the number of valid pairs, we can proceed as follows:
-
Compute the Total Number of Pairs of Uber Edges: The total number of pairs of Uber edges is (\frac{(n - 1) \times (n - 2)}{2}), since there are (n - 1) Uber edges.
-
Compute the Number of Overlapping Pairs: For each edge in the Snap tree, count how many fundamental cycles (Uber edges) include it. This count can be efficiently computed using Euler Tour and Difference Array techniques on trees. Then, for each Snap edge, compute the number of overlapping pairs caused by that edge with the formula: (\text{overlaps} = \frac{c(e) \times (c(e) - 1)}{2}), where (c(e)) is the number of fundamental cycles including (e).
-
Compute the Total Number of Overlapping Pairs: Sum the overlaps over all edges in the Snap tree to get the total number of overlapping pairs.
-
Compute the Total Number of Valid Cycles: Subtract the total number of overlapping pairs from the total number of pairs: [\text{Total Valid Cycles} = \text{Total Pairs} - \text{Total Overlapping Pairs}]
Implementing this requires the following steps:
-
Root the Snap Tree: Arbitrarily choose a root for the Snap tree to facilitate LCA queries.
-
Process Each Uber Edge:
- For each Uber edge, find the LCA of its endpoints in the Snap tree.
- Use a difference array method to add counts to the nodes along the paths from each endpoint to the LCA.
- The counts represent the number of fundamental cycles passing through each node.
-
Post-Order Traversal to Compute Counts:
- Perform a post-order traversal of the Snap tree to compute the cumulative counts at each node and edge.
- The count at each edge represents the number of fundamental cycles that include that edge.
-
Calculate Overlapping Pairs:
- For each edge in the Snap tree, calculate the overlapping pairs using the counts.
-
Output the Result:
- Subtract the total number of overlapping pairs from the total number of pairs to get the number of valid cycles.
Because of the constraints, we need to implement efficient algorithms for LCA queries and tree traversals. Euler Tour and Binary Lifting techniques can be used for O(N log N) time complexity.
Below is the implementation of the above approach:
import sys import threading def main(): import sys import math sys.setrecursionlimit(1 << 25) n = int(sys.stdin.readline()) from collections import defaultdict tree = [[] for _ in range(n)] # Read Snap edges for _ in range(n - 1): u, v = map(int, sys.stdin.readline().split()) u -=1 v -=1 tree[u].append(v) tree[v].append(u) # Build Euler Tour and Sparse Table for LCA euler = [] first_visit = [0]*n depth = [] def dfs(u, p, d): first_visit[u] = len(euler) euler.append(u) depth.append(d) for v in tree[u]: if v != p: dfs(v, u, d+1) euler.append(u) depth.append(d) dfs(0, -1, 0) m = len(euler) log = [0]*(m+1) for i in range(2, m+1): log[i] = log[i >>1] +1 k = log[m] +1 st = [[0]*m for _ in range(k)] st_depth = [[0]*m for _ in range(k)] for i in range(m): st[0][i] = euler[i] st_depth[0][i] = depth[i] for j in range(1, k): for i in range(m - (1<<j)+1): if st_depth[j-1][i] < st_depth[j-1][i + (1<<(j-1))]: st[j][i] = st[j-1][i] st_depth[j][i] = st_depth[j-1][i] else: st[j][i] = st[j-1][i + (1<<(j-1))] st_depth[j][i] = st_depth[j-1][i + (1<<(j-1))] def lca(u, v): fu = first_visit[u] fv = first_visit[v] if fu > fv: fu, fv = fv, fu j = log[fv - fu +1] if st_depth[j][fu] < st_depth[j][fv - (1<<j)+1]: return st[j][fu] else: return st[j][fv - (1<<j)+1] cnt = [0]*n # Read Uber edges and process counts m = n -1 total_pairs = m * (m -1) //2 uber_edges = [] for _ in range(n -1): u, v = map(int, sys.stdin.readline().split()) u -=1 v -=1 uber_edges.append((u,v)) w = lca(u,v) cnt[u] +=1 cnt[v] +=1 cnt[w] -=2 c = [0]*n def dfs2(u, p): for v in tree[u]: if v != p: dfs2(v, u) cnt[u] += cnt[v] dfs2(0, -1) edge_overlaps = 0 def dfs3(u, p): for v in tree[u]: if v != p: c = cnt[v] edge_overlaps += c * (c -1) //2 dfs3(v, u) edge_overlaps = 0 def dfs3(u, p): nonlocal edge_overlaps for v in tree[u]: if v != p: c = cnt[v] edge_overlaps += c * (c -1) //2 dfs3(v, u) dfs3(0, -1) total_cycles = total_pairs - edge_overlaps print(total_cycles) threading.Thread(target=main).start()This solution efficiently counts the number of cycles that meet Amin's criteria within the given constraints.
-