Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define ll long long
- #define ull unsigned long long
- template<typename T>
- inline void read(T&x){
- x=0;T k=1;char gc;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
- }
- const int N=1e5+7;
- int n;
- ll p,A,B;
- inline ll add(ll a,ll b){
- return (a+=b)>=p?a-p:a;
- }
- inline ll sub(ll a,ll b){
- return (a-=b)<0?a+p:a;
- }
- inline ll mul(ll a,ll b){
- ll ans=0;
- if(a<b)swap(a,b);
- while(b){
- if(b&1)ans=add(ans,a);
- a=add(a,a);
- b>>=1;
- }
- return ans;
- }
- inline ll qpow(ll a,ll b){
- ll ans=1;
- while(b){
- if(b&1)ans=mul(ans,a);
- a=mul(a,a);
- b>>=1;
- }
- return ans;
- }
- ll w;
- struct comp{
- ll x,y;
- inline comp(ll a,ll b):x(a),y(b){}
- };
- inline comp operator + (const comp &a,const comp &b){
- return comp(add(a.x,b.x),add(a.y,b.y));
- }
- inline comp operator * (const comp &a,const comp &b){
- return comp(add(mul(a.x,b.x),mul(w,mul(a.y,b.y))),add(mul(a.x,b.y),mul(a.y,b.x)));
- }
- inline comp qpow(comp a,ll b){
- comp ans(1,0);
- while(b){
- if(b&1)ans=ans*a;
- a=a*a;
- b>>=1;
- }
- return ans;
- }
- inline ull rnd0(){
- return rand();
- }
- inline ull rnd1(){
- return (rnd0()<<16)|rnd0();
- }
- inline ull rnd2(){
- return (rnd1()<<32)|rnd0();
- }
- inline ull rnd(ll l,ll r){
- return l+rnd2()%(r-l+1);
- }
- inline ll check(ll x){
- return qpow(x,(p-1)/2);
- }
- inline ll Sqrt(ll x){
- if(x==0)return 0;
- if(check(x)==p-1)return -1;
- ll t=rnd(1,p-1);
- while(1){
- w=sub(mul(t,t),x);
- if(check(w)==p-1)return qpow(comp(t,1),(p+1)/2).x;
- t=rnd(1,p-1);
- }
- }
- int fa[N];
- ll a[N];
- vector<int>G[N];
- ll ans,rt,t1,t2;
- map<ll,int>cnt;
- void dfs(int x){
- if(a[x]==0)ans+=cnt[0];
- else if(~rt){
- ans+=cnt[mul(a[x],t1)];
- if(t2!=t1)ans+=cnt[mul(a[x],t2)];
- }
- cnt[a[x]]++;
- for(int i=0;i<G[x].size();++i){
- dfs(G[x][i]);
- }
- cnt[a[x]]--;
- }
- int main(){
- freopen("mikan.in","r",stdin);
- freopen("mikan.out","w",stdout);
- r(n),r(p),r(A),r(B);
- for(int i=1;i<=n;++i)r(a[i]);
- for(int i=2;i<=n;++i){
- r(fa[i]);
- G[fa[i]].push_back(i);
- }
- rt=Sqrt(sub(mul(A,A),4*B%p));
- (B*=2)%=p;
- B=qpow(B,p-2);
- t1=mul((p-A+rt)%p,B);
- t2=mul((2*p-A-rt)%p,B);
- dfs(1);
- printf("%lld\n",ans);
- }
- /*
- 5 7 5 6
- 4 6 2 2 3
- 1 1 2 2
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement