Submission #890675

#TimeUsernameProblemLanguageResultExecution timeMemory
890675Ahmed57Sprinkler (JOI22_sprinkler)C++17
0 / 100
4051 ms445296 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int dp[200001][41]; int lo[200001][41]; int P[200001],dep[200001]; int Pr[200001][41]; int cnt = 0,n,l; map<int,int> mp[200001]; vector<int> adj[200001]; int h[200001],sz[200001]; int vis[200001]; map<pair<int,int>,int> getIndex; 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); } } long long fast(long long a,long long b){ if(b==0)return 1; long long h = fast(a,b/2);h*=h;h%=l; if(b&1)return (h*a)%l; else return h; } 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]]; } 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); for(int i = 1;i<=n;i++){ for(int j = 0;j<=40;j++)dp[i][j] = 1; if(i<=cnt){ for(int j = 0;j<=40;j++)lo[i-1][j] = 1; } } //cout<<"hhh"<<endl; int q;cin>>q; while(q--){ int ty;cin>>ty; if(ty==1){ int x,d,v; cin>>x>>d>>v; int org = x; for(int j = 0;j<=d;j++)dp[x][j]++; while(P[x]!=-1){ x = P[x]; int w = mp[x][org]; int id = getIndex[{x,w}]; int le = lca(x,org); if(le<=d){ for(int j = 0;j<=d-le;j++){ lo[id][j]*=v;lo[id][j]%=l; dp[x][j]*=v;dp[x][j]%=l; } } } }else{ int x;cin>>x; long long all = (h[x]*dp[x][0])%l; int org = x; while(P[x]!=-1){ x = P[x]; int w = mp[x][org]; int id = getIndex[{x,w}]; int le = lca(x,org); all*=dp[x][le];all%=l; all*=fast(lo[id][le],l-2);all%=l; } cout<<all<<endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...