3393: E.From Tree to Graph
题目描述
Bobo has a tree of n vertices numbered with 0, 1, . . . , (n − 1). He subsequently adds m edges between vertex xi and LCA(xi, yi ) where LCA(xi, yi) is the vertex lying on the unique tree path between vertex xi and yi and closest to the vertex 0.
Let the graph obtained by adding the edges {(x1, LCA(x1, y1)), (x2, LCA(x2, y2)), . . . , (xi , LCA(xi, yi))} to the tree be Gi, and fi(u) be the number of connected components after the removal of vertex u from Gi. Bobo knows that for i {0, 1, 2, . . . , m}
zi = fi(0) ⊕fi(1) ⊕· · · ⊕fi(n − 1).
(⊕ denotes xor.)
Given a, b, x0, y0, he also knows that for i {1, 2, . . . , m},
• xi = (a · xi−1 + b · yi−1 + zi−1) mod n,
• yi = (b · xi−1 + a · yi−1 + zi−1) mod n. Help him to find xm, ym.
输入
The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains six integers n, m, a, b, x0, y0. The i-th of the following (n − 1) lines contains two integers ui and vi, which denotes the tree edge between vertex ui and vi.
输出
For each test case, print two integers which denote xm, ym.
Constraint
• 2 ≤ n ≤ 5000
• 1 ≤ m ≤ n2
• 0 ≤ a, b, x0, y0, ui, vi < n
• The sum of n does not exceed 25, 000.
样例输入 复制
4 1 1 0 2 3
0 1
1 2
0 3
4 2 1 0 2 0
0 1
1 2
2 3
5 25 1 2 3 4
0 1
0 2
1 3
1 4
样例输出 复制
2 3
1 3
1 0