#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
using namespace std;
int n,mod,h[200005],root;
vector<int> muchii[200005];
vector<int> kids[200005];
int d1[200005],dp[21][200005],in[200005],out[200005],timp;
int use[200005],parent[200005],par[200005];
int nr[200005],where[200005];
vector<int> aib[2][200005][41]; /// 0 -> pref, 1 -> suf
bool isancestor(int a,int b)
{
return in[a]<=in[b]&&out[a]>=out[b];
}
int LCA(int a,int b)
{
if(d1[a]>d1[b])
swap(a,b);
if(isancestor(a,b))
return a;
for(int i=18;i>=0;i--)
if(dp[i][a]!=0&&!isancestor(dp[i][a],b))
a=dp[i][a];
return dp[0][a];
}
int dist(int a,int b)
{
int lca=LCA(a,b);
return d1[a]+d1[b]-2*d1[lca];
}
void build(int nod)
{
timp++;
in[nod]=timp;
for(int i=1;i<=20;i++)
dp[i][nod]=dp[i-1][dp[i-1][nod]];
for(int i:muchii[nod])
if(i!=dp[0][nod])
{
dp[0][i]=nod;
d1[i]=d1[nod]+1;
build(i);
}
out[nod]=timp;
}
void dfs1(int nod)
{
nr[nod]=1;
for(int i:muchii[nod])
if(!use[i]&&i!=par[nod])
{
par[i]=nod;
dfs1(i);
nr[nod]+=nr[i];
}
}
int centroid(int nod)
{
par[nod]=0;
dfs1(nod);
int lg=nr[nod];
int r=nod;
while(true)
{
bool bad=0;
for(int i:muchii[r])
if(!use[i]&&par[i]==r&&nr[i]>lg/2)
{
bad=1;
par[r]=i;
par[i]=0;
nr[r]-=nr[i];
nr[i]+=nr[r];
r=i;
break;
}
if(!bad)
break;
}
use[r]=1;
for(int i:muchii[r])
if(!use[i])
{
int x=centroid(i);
kids[r].push_back(x);
}
return r;
}
void dfs(int nod)
{
int cnt=0;
for(int i:kids[nod])
{
cnt++;
where[i]=cnt;
par[i]=nod;
dfs(i);
}
int lg=kids[nod].size();
for(int i=0;i<=1;i++)
for(int j=0;j<=40;j++)
for(int k=0;k<=lg;k++)
aib[i][nod][j].push_back(1);
}
int lsb(int x)
{
return x&(-x);
}
void update(int ind,int cur,int p1,int p2,int val)
{
int lg=kids[cur].size();
for(int i=p1;i<=40;i+=lsb(i))
for(int j=p2;j<=lg;j+=lsb(j))
aib[ind][cur][i][j]=(1LL*aib[ind][cur][i][j]*val)%mod;
}
int query(int ind,int cur,int p1,int p2)
{
int rez=1;
for(int i=p1;i>=1;i-=lsb(i))
for(int j=p2;j>=1;j-=lsb(j))
rez=(1LL*rez*aib[ind][cur][i][j])%mod;
return rez;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>mod;
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
muchii[a].push_back(b);
muchii[b].push_back(a);
}
for(int i=1;i<=n;i++)
cin>>h[i];
d1[1]=0;
build(1);
root=centroid(1);
par[root]=0;
dfs(root);
/*for(int i=1;i<=n;i++)
for(int j=0;j<=40;j++)
add[i][j]=1;*/
int q;
cin>>q;
while(q--)
{
int tip;
cin>>tip;
if(tip==1)
{
int nod,d,val;
cin>>nod>>d>>val;
/*for(int i=1;i<=d;i++)
add[nod][i]=(1LL*add[nod][i]*val)%mod;*/
update(1,nod,40-d+1,1,val);
int cur=nod;
int badind=0;
while(cur!=0)
{
int dmax=d-dist(nod,cur);
if(dmax<0)
break;
if(dmax>=0)
h[cur]=(1LL*h[cur]*val)%mod;
if(dmax>0&&badind!=0)
{
int lg=kids[cur].size();
update(1,cur,40-dmax+1,badind+1,val);
update(0,cur,40-dmax+1,lg-badind+2,val);
}
badind=where[cur];
cur=par[cur];
}
}
if(tip==2)
{
int nod;
cin>>nod;
int ans=h[nod];
int badind=where[nod];
int cur=par[nod];
while(cur!=0)
{
int d=dist(nod,cur);
if(d<=40)
{
int lg=kids[cur].size();
int val=query(1,cur,40-d+1,badind);
ans=(1LL*ans*val)%mod;
val=query(0,cur,40-d+1,lg-badind+1);
ans=(1LL*ans*val)%mod;
}
else
break;
badind=where[cur];
cur=par[cur];
}
cout<<ans<<'\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
413368 KB |
Output is correct |
| 2 |
Correct |
89 ms |
413652 KB |
Output is correct |
| 3 |
Correct |
89 ms |
413524 KB |
Output is correct |
| 4 |
Incorrect |
95 ms |
416308 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
413380 KB |
Output is correct |
| 2 |
Incorrect |
3251 ms |
962484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
413380 KB |
Output is correct |
| 2 |
Incorrect |
3251 ms |
962484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
413524 KB |
Output is correct |
| 2 |
Incorrect |
2463 ms |
962132 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
413520 KB |
Output is correct |
| 2 |
Incorrect |
2639 ms |
959796 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
413368 KB |
Output is correct |
| 2 |
Correct |
89 ms |
413652 KB |
Output is correct |
| 3 |
Correct |
89 ms |
413524 KB |
Output is correct |
| 4 |
Incorrect |
95 ms |
416308 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
