| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1274429 | coderpemula | Sprinkler (JOI22_sprinkler) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
vector<int>v[200001];
ll mod,anu[200001],tree[800001],lazy[800001];
int dp[200001][43][2], par[200001],idx[200001],n;
void propagate(int node, int st, int en){
if(st == en){
//if(st == 1 and en == 1) cout<<"cek : "<<node<<" "<<tree[node]<<endl;
tree[node] = tree[node]*lazy[node]%mod;
lazy[node] = 1;
return;
}
lazy[node*2] = lazy[node*2]*lazy[node]%mod;
lazy[node*2+1] = lazy[node*2+1]*lazy[node]%mod;
lazy[node] = 1;
}
ll query(int node, int st, int en, int idx){
propagate(node,st,en);
if(st > idx or en < idx) return 1;
if(st == en) return tree[node];
int mid = (st+en)/2;
int q1 = query(node*2,st,mid,idx);
int q3 = query(node*2+1,mid+1,en,idx);
return q1*q3%mod;
}
void upd(int node, int st, int en, int L, int R, int val){
propagate(node,st,en);
if(st > R or en < L) return;
if(st >= L and en <= R){
lazy[node] = lazy[node]*val%mod;
propagate(node,st,en);
}
else{
int mid = (st+en)/2;
upd(node*2,st,mid,L,R,val);
upd(node*2+1,mid+1,en,L,R,val);
tree[node] = tree[node*2]*tree[node*2+1]%mod;
}
}
// 0 = left, 1 = right
void dfs(int node){
dp[node][0][0] = dp[node][0][1] = idx[node];
int i;
for(i=1;i<=40;i++) dp[node][i][0] = 1e9, dp[node][i][1] = -1e9;
for(auto x:v[node]){
if(x == par[node]) continue;
par[x] = node;
dfs(x);
for(i=0;i<=40;i++){
if(dp[x][i][0] == 1e9) break;
dp[node][i+1][0] = min(dp[node][i+1][0],dp[x][i][0]);
dp[node][i+1][1] = max(dp[node][i+1][1],dp[x][i][1]);
}
}
}
int pangkat(int base ,int con){
if(con == 0) return 1;
int temp = pangkat(base,con/2);
if(con&1) return temp*temp%mod*base%mod;
return temp*temp%mod;
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int i,j,t,tin=2,x,d,qt;
cin>>n>>mod;
for(i=1;i<n;i++){
cin>>j>>t;
v[j].pb(t);
v[t].pb(j);
}
for(i=1;i<=n;i++) cin>>anu[i];
for(i=1;i<=800000;i++) tree[i] = 1;
for(i=1;i<=800000;i++) lazy[i] = 1;
///cout<<tree[4]<<" TREE 4"<<endl;
queue<int>q;
q.push(1);
idx[1] = 1;
while(!q.empty()){
int node = q.front();
q.pop();
//cout<<node<<endl;
for(auto x:v[node]){
if(idx[x] == 0){
idx[x] = tin;
tin++;
q.push(x);
}
}
}
// for(i=1;i<=n;i++) cout<<idx[i]<<" ";
// cout<<endl;
par[1] = 0;
dfs(1);
//cout<<dp[1][1][0]<<" "<<dp[1][1][1]<<endl;
cin>>qt;
vector<int>tmp;
while(qt--){
cin>>t;
if(t == 1){
cin>>x>>d>>j;
int dist = d,node=x, str = 0;
while(true){
if(par[node] == 0 or dist == 0) break;
tmp.pb(node);
dist--;
node = par[node];
}
tmp.pb(node);
while(!tmp.empty()){
node = tmp.back();
tmp.pop_back();
//cout<<node<<" "<<str<<" "<<dist<<endl
bool aseli = false;;
for(i=str;i<=dist;i++){
if(dp[node][i][0] == 1e9){
aseli = true;
break;
}
//cout<<dp[node][i][0]<<" cek "<<dp[node][i][1]<<" "<<j<<endl;
upd(1,1,n,dp[node][i][0],dp[node][i][1],j);
}
if(aseli) break;
str = dist;
dist++;
}
tmp.clear();
}
else cin>>j, cout<<anu[j]*query(1,1,n,idx[j])%mod<<"\n";
}
return 0;
}