| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 998462 | efishel | Sprinkler (JOI22_sprinkler) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Sprinkler Saul
#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define pb push_back
#define pll pair<ll, ll>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define repa(a,b) for(auto a:b)
#define endl "\n"
using namespace std;
const int lim=2e5+5;
vector<int> adj[lim];
int sz[lim], h[lim][20], pos[lim], sum[20], lvl[lim], mx[lim];
pll par[lim];
ll L, H[lim];
bool vis[lim];
struct segtree{
segtree *left, *right;
int l, r, mid;
ll v=1;
segtree(int x=0, int y=lim): l(x), r(y){
if(l==r) return;
mid=((l+r)>>1);
left = new segtree(l,mid);
right= new segtree(mid+1,r);
}
void update(int x, int y, ll z){
if(y<l || r<x) return;
if(x<=l && r<=y){
v*=z;
v%=L;
return;
}
left->update(x,y,z);
right->update(x,y,z);
}
ll query(int x){
if(x<l || r<x) return 1;
if(x<=l && r<=x) return v;
return (((left->query(x)*right->query(x))%L)*v)%L;
}
} ST[20];
void sztree(int u, int p=0){
sz[u]=1;
repa(v,adj[u]){
if(v==p || vis[v]) continue;
sztree(v,u);
sz[u]+=sz[v];
}
}
void dis(int u, int l){
int x=0, d;
queue<int> q;
q.push(u);
q.push(0);
h[u][l]=0;
while(q.size()){
x=q.front();
q.pop();
d=q.front();
q.pop();
repa(y,adj[x]){
if(h[y][lvl[u]]>d+1){
h[y][lvl[u]]=d+1;
q.push(y);
q.push(d+1);
}
}
}
pos[u]=sum[l]+1;
sum[l]+=d;
mx[u]=d;
}
pll find_centroid(int u, int p, int r){
repa(v,adj[u]){
if(v==p || vis[v]) continue;
if(sz[v]>sz[r]/2){
pll x=find_centroid(v,u,r);
return {x.fi,x.se+1};
}
}
return {u,0};
}
void centroid(int u, int p=0, int l=0){
sztree(u);
pll x=find_centroid(u,p,u);
u=x.fi;
lvl[u]=l;
par[u]={p,x.se+1};
dis(u,l);
vis[u]=true;
repa(v,adj[u]) if(!vis[v]) centroid(v,u,l+1);
}
void update(int u, int d, ll w){
pll x=par[u];
while(x.fi){
if(h[u][lvl[x.fi]]<=d){
H[x.fi]*=w;
H[x.fi]%=L;
ST[lvl[x.fi]].update(pos[x.fi],pos[x.fi]+max(0ll,(min(d-h[x.fi][lvl[x.fi]],mx[x.fi])),w);
}
x={par[x.fi].fi,par[x.fi].se+x.se};
}
ST[lvl[u]].update(pos[u],pos[u]+min(d,mx[u]),w);
}
ll query(int u){
pll x={u,0};
ll ans=H[u];
while(x.fi){
ans*=ST[lvl[x.fi]].query(pos[x.fi]+h[u][lvl[x.fi]]);
ans%=L;
x=par[x.fi];
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n, m, u, v;
cin>>n>>L;
rep(i,0,lim) rep(j,0,20) h[i][j]=1e9;
rep(i,1,n){
cin>>u>>v;
adj[u].pb(v);
adj[v].pb(u);
}
rep(i,0,n) cin>>H[i+1];
centroid(u);
int q;
cin>>q;
while(q--){
ll t, x, d, w;
cin>>t;
if(t&1){
cin>>x>>d>>w;
update(x,d,w);
}else{
cin>>x;
cout<<query(x)<<endl;
}
}
}