From Tree to Graph
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 327680/327680 K (Java/Others)Total Submission(s): 11 Accepted Submission(s): 6
Problem Description
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}
( ⊕ 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)modn,
* yi=(b⋅xi−1+a⋅yi−1+zi−1)modn.
Help him to find xm, ym.
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)modn,
* yi=(b⋅xi−1+a⋅yi−1+zi−1)modn.
Help him to find xm, ym.
Input
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.
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.
Output
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.
## Constraint
* 2≤n≤5000
* 1≤m≤n2
* 0≤a,b,x0,y0,ui,vi<n
* The sum of n does not exceed 25,000.
Sample Input
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
Sample Output
2 3 1 3 1 0
题意：zi的意思是根据题目要求，添加若干条边后的图，去掉任意一个点，之后的联通分量的异或和。然后根据这个zi，更新x,y。最后求第m个x,y。注意G0是原图。
解题思路：首先求出z0，这个直接对每一个点的出入度之和计算异或和即可。然后开始加边，每一次加边，必定会形成环，然后我们用并查集对这个环进行缩点！缩点后，环内的点会影响答案，环外的点对答案无影响，所以我们只需要暴力对环内的点计算对答案的影响即可，这里可以用异或的性质来计算（两个相同的异或会抵消）。要注意各种细节，用并查集往上走时，有可能会跳过LCA，所以要用dep来判断是否结束暴力。注意所有的判断都是对父亲进行的。这里的点是从0开始，要转换成1开始。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
const int MAXLOGV=20;
vector<int> G[MAXN];
int N;
/****LCA****/
int f[MAXLOGV+2][MAXN];
int dep[MAXN];
void dfs(int u,int fa)
{
f[0][u]=fa;dep[u]=dep[fa]+1;
for(int i=0;i<G[u].size();++i){
int v=G[u][i];
if(v==fa) continue;
dfs(v,u);
}
}
void lca_init(){
memset(f,0,sizeof(f));
dep[0]=0;
dfs(1,0);
for(int k=0;k+1<MAXLOGV;++k){
for(int v=1;v<=N;++v){
if(f[k][v]==0) f[k+1][v]=0;
else f[k+1][v]=f[k][f[k][v]];
}
}
}
int LCA(int u,int v)
{
if(dep[u]>dep[v]) swap(u,v);
for(int k=0;k<MAXLOGV;++k){
if( (dep[v]-dep[u])>>k&1){
v=f[k][v];
}
}
if(u==v) return u;
for(int k=MAXLOGV-1;k>=0;--k){
if(f[k][u]!=f[k][v]){
u=f[k][u];
v=f[k][v];
}
}
return f[0][u];
}
/****LCA****/
int sz[MAXN];
int ans=0;
int pre[MAXN];
int find(int x){
return pre[x]==x?x:pre[x]=find(pre[x]);
}
void init(){
ans=0;
for(int i=0;i<=N;i++){
G[i].clear();
pre[i]=i;
}
}
void link(int x,int y){
x=find(x);
if(dep[f[0][x]]<=dep[y]||f[0][x]==0)//不能用f[0][x]==y
{
return;
}
ans=ans^sz[f[0][x]]^(sz[f[0][x]]-1);
sz[f[0][x]]--;
pre[x]=f[0][x];
link(f[0][x],y);
}
int main(){
int m,a,b,x,y;
while(~scanf("%d%d%d%d%d%d",&N,&m,&a,&b,&x,&y)){
int u,v;
init();
for(int i=1;i<N;i++){
scanf("%d%d",&u,&v);
u++;
v++;
G[u].push_back(v);
G[v].push_back(u);
}
lca_init();
for(int i=1;i<=N;i++){
sz[i]=G[i].size();
ans^=sz[i];
}
for(int i=0;i<m;i++){
int nx=(a*x+b*y+ans)%N;
int ny=(b*x+a*y+ans)%N;
x=nx;
y=ny;
link(x+1,LCA(x+1,y+1));
}
printf("%d %d\n",x,y);
}
}