#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;
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 aib[200005];
int qry(int poz)
{
int aux=1;
for(int i=poz;i>0;i-=(i&(-i)))
aux = (aux * aib[i])%MOD;
return aux;
}
void upd(int poz, int newv)
{
for(int i=poz;i<=n;i+=(i&(-i)))
aib[i] = (aib[i] * newv)%MOD;
}
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] = INF;
tori[nod][d] = -INF;
}
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]);
}
}
}
}
int inm[200005];
int imp[200005];
void faupd(int le, int ri, int newv, int inv)
{
if(le>ri)
return;
inm[le] = inm[le]*newv;
imp[ri+1] = imp[ri+1]*newv;
upd(le,newv);
upd(ri+1,inv);
}
int qry_brut(int poz)
{
int rez=1;
for(int i=1;i<=poz;i++)
{
rez = rez * inm[i];
rez = rez / imp[i];
}
return rez;
}
int calc_phi(int x)
{
return x-2;
}
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];
aib[i]=1;
inm[i]=1;
imp[i]=1;
}
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;
for(int j=0;j<=d-i;j++)
{
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];
}
int inv=put(b,phi-1);
for(int i=max((int)1,depth[a]-d);i<=min(n,depth[a]+d);i++)
{
faupd(le[i],ri[i],b,inv);
}
}
else
{
cin>>a;
cout<<(h[a]*qry_brut(pos[a]))%MOD<<"\n";
//cout<<h[a]<<" "<<qry_brut(pos[a])<<" zzz\n";
}
}
return 0;///schimba aibu cu aint in cazurile in care ai updateuri care inmultesc cu 0 -----------------------------------------------------------------------
}
/**
le_d = min(tole[ancestor_i][])
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
46324 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
22872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
