This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,MOD,phi;
int put(int a, int exp)
{
if(exp==0)
return 1;
if(exp%2==0)
return put((a*a)%MOD,exp/2);
else
return (put((a*a)%MOD,exp/2)*a)%MOD;
}
int aint[800005];
int lazy[800005];
void build(int nod, int st, int dr)
{
aint[nod]=1;
lazy[nod]=1;
if(st==dr)
return;
int mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
}
void propagate(int nod)
{
lazy[nod*2]=lazy[nod*2]*lazy[nod]%MOD;
lazy[nod*2+1]=lazy[nod*2+1]*lazy[nod]%MOD;
aint[nod*2]=aint[nod*2]*lazy[nod]%MOD;
aint[nod*2+1]=aint[nod*2+1]*lazy[nod]%MOD;
lazy[nod]=1;
}
void upd(int nod, int st, int dr, int le, int ri, int newv)
{
if(le>ri)
return;
if(le==st && dr==ri)
{
aint[nod]=aint[nod]*newv%MOD;
lazy[nod]=lazy[nod]*newv%MOD;
return;
}
propagate(nod);
int mij=(st+dr)/2;
upd(nod*2,st,mij,le,min(mij,ri),newv);
upd(nod*2+1,mij+1,dr,max(le,mij+1),ri,newv);
aint[nod]=aint[nod*2]*aint[nod*2+1]%MOD;
}
int qry(int nod, int st, int dr, int poz)
{
if(st==dr)
return aint[nod];
propagate(nod);
int mij=(st+dr)/2;
if(poz<=mij) return qry(nod*2,st,mij,poz);
else return qry(nod*2+1,mij+1,dr,poz);
}
int aib0[200005];
int qry0(int poz)
{
int aux=0;
for(int i=poz;i>0;i-=(i&(-i)))
aux+=aib0[i];
return aux;
}
void upd0(int poz, int newv)
{
for(int i=poz;i<=n;i+=(i&(-i)))
aib0[i]+=newv;
}
int h[200005];
vector<int> con[200005];
int parent[200005];
int tole[200005][45];
int tori[200005][45];
int cntd[200005];
int cntd2[200005];
int depth[200005];
int pos[200005];
void dfs(int nod)
{
cntd[depth[nod]]++;
for(auto adj:con[nod])
{
if(adj!=parent[nod])
{
depth[adj]=depth[nod]+1;
parent[adj]=nod;
dfs(adj);
}
}
}
void dfs2(int nod)
{
cntd2[depth[nod]]++;
pos[nod] = cntd[depth[nod]-1] + cntd2[depth[nod]];
//cout<<nod<<" "<<pos[nod]<<" pos\n";
for(int d=0;d<=42;d++)
{
tole[nod][d] = n+5;
tori[nod][d] = -1;
}
tole[nod][0] = tori[nod][0] = pos[nod];
for(auto adj:con[nod])
{
if(adj!=parent[nod])
{
dfs2(adj);
for(int d=1;d<=42;d++)
{
tole[nod][d] = min(tole[nod][d], tole[adj][d-1]);
tori[nod][d] = max(tori[nod][d], tori[adj][d-1]);
}
}
}
}
void faupd(int le, int ri, int newv)
{
if(le>ri)
return;
if(newv!=0)
{
upd(1,1,n,le,ri,newv);
}
else
{
upd0(le,1);
upd0(ri+1,-1);
}
}
int calc_phi(int x)
{
int d=2,prod=x;
while(d*d<=x)
{
if(x%d==0)
{
while(x%d==0)
x/=d;
prod = prod / d * (d-1);
}
if(d==2)
d--;
d+=2;
}
if(x>1)
prod = prod / x * (x-1);
return prod;
}
int getrez(int poz)
{
if(qry0(poz)>0)
return 0;
else
return qry(1,1,n,poz);
}
int le[200005],ri[200005];
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>MOD;
phi = calc_phi(MOD);
int a,b;
for(int i=1;i<n;i++)
{
cin>>a>>b;
con[a].push_back(b);
con[b].push_back(a);
}
depth[1]=1;
dfs(1);
for(int i=2;i<=n;i++)
cntd[i]+=cntd[i-1];
dfs2(1);
for(int i=1;i<=n;i++)
{
cin>>h[i];
}
build(1,1,n);
int cntq,tip,d;
cin>>cntq;
for(int pas=1;pas<=cntq;pas++)
{
cin>>tip;
if(tip==1)
{
cin>>a>>d>>b;
for(int i=max((int)1,depth[a]-d);i<=min(n,depth[a]+d);i++)
{
le[i]=n+5;
ri[i]=-1;
}
int cur=a;
for(int i=0;i<=d;i++)
{
if(cur==0)
break;
///j > -1 + d - (i+1)
int lim=0;
if(parent[cur]!=0)
lim=max(lim, d - i - 1);
for(int j=lim;j<=d-i;j++)
{
if(depth[cur]+j>n)
break;
le[depth[cur]+j] = min(le[depth[cur]+j], tole[cur][j]);
ri[depth[cur]+j] = max(ri[depth[cur]+j], tori[cur][j]);
}
cur = parent[cur];
}
for(int i=max((int)1,depth[a]-d);i<=min(n,depth[a]+d);i++)
{
faupd(le[i],ri[i],b);
}
}
else
{
cin>>a;
cout<<(h[a]*getrez(pos[a]))%MOD<<"\n";
//cout<<h[a]<<" "<<qry_brut(pos[a])<<" zzz\n";
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |