#include <bits/stdc++.h>
using namespace std;
int P[200001],dep[200001];
int Pr[200001][41],q;
int cnt = 1,n,L;
map<int,int> mp[200001];
vector<int> adj[200001];
int h[200001],sz[200001];
bool vis[200001];
map<pair<int,int>,int> getIndex;
vector<array<int,3>>Lol[200001],LOL[200001];
vector<array<int,2>>QU[200001],qu[200001];
int dfs(int i,int pr){
sz[i] = 1;
for(auto j:adj[i]){
if(j==pr||vis[j])continue;
sz[i]+=dfs(j,i);
}
return sz[i];
}
int getCen(int i,int pr,int ss){
for(auto j:adj[i]){
if(j==pr||vis[j])continue;
if(sz[j]*2>ss)return getCen(j,i,ss);
}
return i;
}
void lol(int i,int pr,int co,int de){
mp[de][i] = co;
for(auto j:adj[i]){
if(j==pr||vis[j])continue;
lol(j,i,co,de);
}
}
void centroid(int i,int pr){
int cen = getCen(i,i,dfs(i,i));
vis[cen] = 1;
P[cen] = pr;
for(auto j:adj[cen]){
if(vis[j])continue;
lol(j,cen,j,cen);
getIndex[{cen,j}] = cnt++;
}
for(auto j:adj[cen]){
if(vis[j])continue;
centroid(j,cen);
}
}
void init(int i,int pr){
Pr[i][0] = pr;
dep[i] = dep[pr]+1;
for(int j = 1;j<19;j++){
Pr[i][j] = Pr[Pr[i][j-1]][j-1];
}
for(auto j:adj[i]){
if(j==pr)continue;
init(j,i);
}
}
int lca(int a,int b){
int sum = dep[a]+dep[b];
if(dep[a]<dep[b])swap(a,b);
for(int j = 18;j>=0;j--){
if(dep[Pr[a][j]]>=dep[b])a = Pr[a][j];
}
if(a==b){
return sum-2*dep[a];
}
for(int j = 18;j>=0;j--){
if(Pr[a][j]!=Pr[b][j]){
a = Pr[a][j];
b = Pr[b][j];
}
}
return sum-2*dep[Pr[a][0]];
}
int seg[1600001][41*4+1];
void build2(int p,int l,int r,int ty){
if(l==r){
seg[ty][p] = 1;
return;
}
int md = (l+r)/2;
build2(p*2,l,md,ty);
build2(p*2+1,md+1,r,ty);
seg[ty][p] = (seg[ty][p*2]*seg[ty][p*2+1])%L;
}
void merge(int p,int l,int r,int p1,int p2,int ty){
if(l==r){
seg[ty][p] = (seg[p1][p]*seg[p2][p])%L;
return ;
}
int md = (l+r)/2;
merge(p*2,l,md,p1,p2,ty);
merge(p*2+1,md+1,r,p1,p2,ty);
seg[ty][p] = (seg[p1][p]*seg[p2][p])%L;
}
void build(int p,int l,int r){
if(l==r){
build2(1,0,40,p);
return ;
}
int md = (l+r)/2;
build(p*2,l,md);build(p*2+1,md+1,r);
merge(1,0,40,p*2,p*2+1,p);
return ;
}
void update2(int p,int l,int r,int idx,int val,int ty){
if(l==r){
seg[ty][p]*=val;seg[ty][p]%=L;
//cout<<seg[ty][p]<<endl;
return ;
}
int md = (l+r)/2;
if(idx<=md)update2(p*2,l,md,idx,val,ty);
else update2(p*2+1,md+1,r,idx,val,ty);
seg[ty][p] = (seg[ty][p*2]*seg[ty][p*2+1])%L;
}
void update(int p,int l,int r,int idx,int val,int ty){
if(l==r){
update2(1,0,40,ty,val,p);
return ;
}
int md = (l+r)/2;
if(idx<=md)update(p*2,l,md,idx,val,ty);
else update(p*2+1,md+1,r,idx,val,ty);
merge(1,0,40,p*2,p*2+1,p);
}void set2(int p,int l,int r,int idx,int ty){
if(l==r){
seg[ty][p] = 1;seg[ty][p]%=L;
return ;
}
int md = (l+r)/2;
if(idx<=md)set2(p*2,l,md,idx,ty);
else set2(p*2+1,md+1,r,idx,ty);
seg[ty][p] = (seg[ty][p*2]*seg[ty][p*2+1])%L;
}
void sett(int p,int l,int r,int idx,int ty){
if(l==r){
set2(1,0,40,ty,p);
return;
}
int md = (l+r)/2;
if(idx<=md)sett(p*2,l,md,idx,ty);
else sett(p*2+1,md+1,r,idx,ty);
merge(1,0,40,p*2,p*2+1,p);
}
int query2(int p,int l,int r,int lq,int rq,int ty){
if(l>=lq&&r<=rq){
return seg[ty][p];
//cout<<seg[ty][p]<<endl;
//assert(seg[ty][p]);
}
if(r<lq||l>rq){
//cout<<1<<endl;
return 1;
}
int md = (l+r)/2;
return (query2(p*2,l,md,lq,rq,ty)*query2(p*2+1,md+1,r,lq,rq,ty))%L;
}
int query(int p,int l,int r,int lq,int rq,int ty){
if(r<lq||l>rq||lq>rq)return 1;
if(l>=lq&&r<=rq){
return query2(1,0,40,ty,2,p);
}
int md = (l+r)/2;
return (query(p*2,l,md,lq,rq,ty)*query(p*2+1,md+1,r,lq,rq,ty))%L;
}
long long ANS[400001];
void comp(int i){
int cen = getCen(i,i,dfs(i,i));
vis[cen] = 1;
for(auto j:LOL[cen]){
update(1,1,q,j[0],j[2],j[1]);
//cout<<"hh"<<endl;
}
for(auto j:adj[cen]){
if(vis[j])continue;
for(auto e:qu[getIndex[{cen,j}]]){
ANS[e[0]]*=query(1,1,q,1,e[0],e[1]);
ANS[e[0]]%=L;
//cout<<query(1,1,q,1,e[0],e[1])<<"hhhh"<<endl;
}
for(auto e:Lol[getIndex[{cen,j}]]){
update(1,1,q,e[0],e[2],e[1]);
//cout<<"hh"<<endl;
}
}
for(auto e:QU[cen]){
ANS[e[0]]*=query(1,1,q,1,e[0],e[1]);
ANS[e[0]]%=L;
}
for(auto j:LOL[cen]){
sett(1,1,q,j[0],j[1]);
}
for(auto j:adj[cen]){
if(vis[j])continue;
for(auto e:Lol[getIndex[{cen,j}]]){
sett(1,1,q,e[0],e[1]);
}
}
reverse(adj[cen].begin(),adj[cen].end());
for(auto j:adj[cen]){
if(vis[j])continue;
for(auto e:qu[getIndex[{cen,j}]]){
ANS[e[0]]*=query(1,1,q,1,e[0],e[1]);
ANS[e[0]]%=L;
}
for(auto e:Lol[getIndex[{cen,j}]]){
update(1,1,q,e[0],e[2],e[1]);
}
}for(auto j:adj[cen]){
if(vis[j])continue;
for(auto e:Lol[getIndex[{cen,j}]]){
sett(1,1,q,e[0],e[1]);
}
}
reverse(adj[cen].begin(),adj[cen].end());
for(auto j:adj[cen]){
if(vis[j])continue;
comp(j);
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
//freopen("input.txt","r",stdin);
//freopen("outout.txt","w",stdout);
cin>>n>>L;
for(int i = 0;i<n-1;i++){
int a,b;cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i = 1;i<=n;i++){
cin>>h[i];
}
//cout<<"hhh"<<endl;
init(1,1);
//cout<<"hhh"<<endl;
centroid(1,-1);
//cout<<"hhh"<<endl;
cin>>q;
build(1,1,q);
//cout<<seg[1][1]<<endl;
vector<int> lw;
for(int Q = 1;Q<=q;Q++){
int ty;cin>>ty;
if(ty==1){
int x,d,v;
cin>>x>>d>>v;
int org = x;
LOL[x].push_back({Q,d,v});
while(P[x]!=-1){
x = P[x];
int w = mp[x][org];
int id = getIndex[{x,w}];
//cout<<x<<"x"<<q<<" "<<id<<endl;
int le = lca(x,org);
if(le<=d){
Lol[id].push_back({Q,d-le,v});
}
}
}else{
int x;cin>>x;
lw.push_back(Q);
ANS[Q] = h[x];
QU[x].push_back({Q,0});
int org = x;
while(P[x]!=-1){
x = P[x];
int w = mp[x][org];
int id = getIndex[{x,w}];
//cout<<x<<"hhh "<<id<<endl;
int le = lca(x,org);
qu[id].push_back({Q,le});
//cout<<ma[x]<<endl;
//cout<<dp[x][le]<<" "<<query(1,1,n,mi[x],id-1,le)<<" "<<query(1,1,n,id+1,ma[x],le)<<endl;
}
}
}
//cout<<"hhh"<<endl;
for(int i = 1;i<=n;i++)vis[i] =0;
comp(1);
sort(lw.begin(),lw.end());
//cout<<"***********************"<<endl;
for(auto i:lw){
cout<<ANS[i]<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
39256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
39384 KB |
Output is correct |
| 2 |
Execution timed out |
4099 ms |
902768 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
39384 KB |
Output is correct |
| 2 |
Execution timed out |
4099 ms |
902768 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
39256 KB |
Output is correct |
| 2 |
Execution timed out |
4066 ms |
947172 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
39260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
39256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
