#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5+5,inf=1e18,minf=-1e18,lg=30;
//#undef int
int n,k,m;
vector<int>adj[mxn+10];
void setIO(string name){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
int h[mxn+10],dist[mxn+10],sz[mxn+10],del[mxn+10],id[mxn+10];
struct qry{
int time,node,D,w,type;
bool operator<(qry a)const{return D-dist[node]<=a.D-dist[a.node];};
};
vector<qry>have[mxn+10];
vector<qry>event,event2;
struct fen{
int fwk[mxn+10];
void init(int n){for(int i=0;i<=n;i++)fwk[i]=1;}
void update(int pos,int val,int n){for(int i=pos;i<=n;i+=(i&-i))fwk[i]=(fwk[i]*val)%k;}
int qry(int pos){
if(pos==0)return 1;
int ans=1;
for(int i=pos;i>0;i-=(i&-i))ans=(ans*fwk[i])%k;
return ans;
}
}t;
vector<qry>bro[mxn+10];
void getsz(int cur,int p){
sz[cur]=1,dist[cur]=0;
for(auto i:adj[cur])if(i!=p&&!del[i])getsz(i,cur),sz[cur]+=sz[i];
}
int getcen(int cur,int p,int need){
for(auto i:adj[cur])if(i!=p&&sz[i]>=need&&!del[i])return getcen(i,cur,need);
return cur;
}
int in[mxn+10],where[mxn+10],ans[mxn+10];
int inv(int x){
x%=k;
int ex=k-2,ans=1;
while(ex){
if(ex&1)ans=(ans*x)%k;
x=(x*x)%k;
ex>>=1;
}
return ans;
}
void dfs(int cur,int p,int deg){
for(auto i:have[cur]){
if(i.type==1){
if(i.D-dist[cur]>=0)event2.pb(i),event.pb(i),bro[deg].pb(i);
}
else event.pb(i),bro[deg].pb(i);
}
for(auto i:adj[cur])if(i!=p&&!del[i]){
dist[i]=dist[cur]+1;
dfs(i,cur,deg);
}
}
bool cmp(qry a,qry b){return a.time<b.time;}
void solve(int cur){
getsz(cur,-1);
int node=getcen(cur,-1,sz[cur]/2);
dist[node]=0;
for(auto i:have[node]){
if(i.type==1){
if(i.D-dist[node]>=0)event2.pb(i),event.pb(i);
}
else event.pb(i);
}
//cout<<cur<<" "<<node<<'\n';
for(int i=0;i<adj[node].size();i++)if(!del[adj[node][i]])dist[adj[node][i]]=1,dfs(adj[node][i],node,i);
sort(rall(event2));
for(int i=0;i<event2.size();i++)id[event2[i].time]=i+1;
t.init(event2.size());
int last=inf;
for(auto i:event2){
if(i.D-dist[i.node]>last)assert(0);
last=i.D-dist[i.node];
}
// for(auto i:event2)cout<<i.time<<" "<<i.D<<" "<<i.w<<' '<<dist[i.node]<<' '<<i.node<<"LLL\n";
auto get=[&](int x){
int l=0,r=event2.size()-1,pos=minf;
while(l<=r){
int mid=l+(r-l)/2;
if(event2[mid].D-dist[event2[mid].node]>=x)l=mid+1,pos=max(pos,mid);
else r=mid-1;
}
if(pos==minf)return 0LL;
return pos+1;
};
sort(all(event),cmp);
last=minf;
for(auto i:event){
if(i.time<=last)assert(0);
last=i.time;
if(i.type==1&&id[i.time]!=-1)t.update(id[i.time],i.w,event2.size());
else if(i.type==2){
where[i.time]=get(dist[i.node]);
ans[i.time]=(ans[i.time]%k*t.qry(where[i.time])%k)%k;
}
}
t.init(event2.size());
for(int i=0;i<adj[node].size();i++)if(!del[adj[node][i]]){
sort(all(bro[i]),cmp);
last=minf;
for(auto j:bro[i]){
if(j.time<=last)assert(0);
last=j.time;
if(j.type==1&&id[j.time]!=-1)t.update(id[j.time],j.w,event2.size());
else if(j.type==2)ans[j.time]=(ans[j.time]%k*inv(t.qry(where[j.time])%k))%k;
}
}
event2.clear();
event.clear();
del[node]=1;
for(int i=0;i<adj[node].size();i++)bro[i].clear();
for(auto i:adj[node])if(!del[i])solve(i);
}
int32_t main(){
fastio
cin>>n>>k;
for(int i=0;i<n-1;i++){
int a,b;cin>>a>>b;
adj[a].pb(b);
adj[b].pb(a);
}
for(int i=1;i<=n;i++)cin>>h[i];
int q;cin>>q;
vector<int>what;
for(int i=0;i<q;i++){
int a;cin>>a;
qry x;
x.type=a;
x.time=i;
if(a==1){
cin>>x.node>>x.D>>x.w;
have[x.node].pb(x);
}
else{
cin>>x.node;
have[x.node].pb(x);
what.pb(i);
ans[i]=h[x.node];
}
}
solve(1);
for(auto i:what)cout<<ans[i]<<"\n";
//solve(1);
}
/*
4 7
1 2
2 3
3 4
1
1
1
1
11
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
1 4 10 2
2 1
2 2
2 3
2 4
*/
Compilation message
sprinkler.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize ("03,unroll-lopps")
| ^
sprinkler.cpp:39:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
39 | void setIO(string name){
| ^
sprinkler.cpp:47:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
47 | bool operator<(qry a)const{return D-dist[node]<=a.D-dist[a.node];};
| ^~~~~
sprinkler.cpp:53:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
53 | void init(int n){for(int i=0;i<=n;i++)fwk[i]=1;}
| ^
sprinkler.cpp:54:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
54 | void update(int pos,int val,int n){for(int i=pos;i<=n;i+=(i&-i))fwk[i]=(fwk[i]*val)%k;}
| ^
sprinkler.cpp:55:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
55 | int qry(int pos){
| ^
sprinkler.cpp:63:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
63 | void getsz(int cur,int p){
| ^
sprinkler.cpp:67:34: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
67 | int getcen(int cur,int p,int need){
| ^
sprinkler.cpp:72:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
72 | int inv(int x){
| ^
sprinkler.cpp:82:31: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
82 | void dfs(int cur,int p,int deg){
| ^
sprinkler.cpp:94:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
94 | bool cmp(qry a,qry b){return a.time<b.time;}
| ^
sprinkler.cpp:95:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
95 | void solve(int cur){
| ^
sprinkler.cpp: In function 'void solve(long long int)':
sprinkler.cpp:106:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int i=0;i<adj[node].size();i++)if(!del[adj[node][i]])dist[adj[node][i]]=1,dfs(adj[node][i],node,i);
| ~^~~~~~~~~~~~~~~~~
sprinkler.cpp:108:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i=0;i<event2.size();i++)id[event2[i].time]=i+1;
| ~^~~~~~~~~~~~~~
sprinkler.cpp:116:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
116 | auto get=[&](int x){
| ^
sprinkler.cpp:138:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int i=0;i<adj[node].size();i++)if(!del[adj[node][i]]){
| ~^~~~~~~~~~~~~~~~~
sprinkler.cpp:151:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for(int i=0;i<adj[node].size();i++)bro[i].clear();
| ~^~~~~~~~~~~~~~~~~
sprinkler.cpp: At global scope:
sprinkler.cpp:154:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
154 | int32_t main(){
| ^
sprinkler.cpp: In function 'void setIO(std::string)':
sprinkler.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:42:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24152 KB |
Output is correct |
| 2 |
Correct |
4 ms |
24152 KB |
Output is correct |
| 3 |
Correct |
3 ms |
24156 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
24668 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24156 KB |
Output is correct |
| 2 |
Incorrect |
686 ms |
110072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24156 KB |
Output is correct |
| 2 |
Incorrect |
686 ms |
110072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
24152 KB |
Output is correct |
| 2 |
Incorrect |
457 ms |
113296 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24152 KB |
Output is correct |
| 2 |
Incorrect |
511 ms |
117808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
24152 KB |
Output is correct |
| 2 |
Correct |
4 ms |
24152 KB |
Output is correct |
| 3 |
Correct |
3 ms |
24156 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
24668 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
