Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- using namespace std;
- const int N=400001;
- int n,logTable[N+1],f[22][N],first[N],h[N];
- vector <int> order,g[N];
- void dfs(int v,int cur)
- {
- h[v]=cur;
- first[v]=(int)order.size();
- order.push_back(v);
- for(size_t i=0;i<g[v].size();i++)
- if (h[g[v][i]]==-1)
- {
- dfs(g[v][i],cur+1);
- order.push_back(v);
- }
- }
- int get_ans(int i,int j)
- {
- if (i>j) swap(i,j);
- int k=logTable[j-i];
- int x=f[k][i];
- int y=f[k][j-(1<<k)+1];
- return h[order[x]]<=h[order[y]]?order[x]:order[y];
- }
- void sparse_table()
- {
- f[0][0]=0;
- f[0][1]=1;
- for(int i=2;i<=n;i++)
- {
- logTable[i]=logTable[i>>1]+1;
- f[0][i]=i;
- }
- for(int k=1;(1<<k)<n;k++)
- for(int i=0;i+(1<<k)<=n;i++)
- {
- int x=f[k-1][i];
- int y=f[k-1][i+(1<<k-1)];
- f[k][i]=h[order[x]]<=h[order[y]]?x:y;
- }
- }
- int main()
- {
- int m,v;
- long long sum=0,x,y,z,a1,a2;
- scanf("%d%d",&n,&m);
- for(int i=0;i<n-1;i++)
- {
- scanf("%d",&v);
- g[v].push_back(i+1);
- g[i+1].push_back(v);
- first[i]=h[i]=-1;
- }
- first[n-1]=h[n-1]=-1;
- cin>>a1>>a2>>x>>y>>z;
- dfs(0,0);
- sparse_table();
- sum+=v=get_ans(first[a1],first[a2]);
- for(int i=3;i<=(m<<1);i++)
- if (i&1) a1=(a1*x+a2*y+z)%n; else sum+=v=get_ans(first[(a1+v)%n],first[a2=(a2*x+a1*y+z)%n]);
- cout<<sum;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement