#include <bits/stdc++.h>
bool home = 1;
using namespace std;
typedef long long ll;
const int N=200000+7;
const int K=20;
int n;
int q;
int mod;
int mod_phi;
int h[N];
vector<int> g[N];
pair<int, int> rmq[K][2*N];
int lg[2*N];
int par[N];
int dep[N];
int first_euler[N];
int last_euler[N];
vector<int> la[N];
int top;
int verts[N];
int pos[N];
void build(int a,int p=-1){
par[a]=p;
la[dep[a]].push_back(a);
rmq[0][++top]={dep[a], a};
first_euler[a]=last_euler[a]=top;
for(auto&b:g[a]){
if(b==p) continue;
dep[b]=1+dep[a];
build(b,a);
rmq[0][++top]={dep[a], a};
last_euler[a]=top;
}
}
int get_lca(int a,int b){
if(first_euler[a]>last_euler[b]) swap(a,b);
a=first_euler[a];
b=last_euler[b];
assert(a<=b);
int k=lg[b-a+1];
return min(rmq[k][a],rmq[k][b-(1<<k)+1]).second;
}
int get_dist(int a,int b){
int c=get_lca(a,b);
return dep[a]+dep[b]-2*dep[c];
}
int cnt_at_dep_before(int dep,int when) {
int low=0,high=(int)la[dep].size()-1,sol=0;
while(low<=high){
int mid=(low+high)/2;
if(first_euler[la[dep][mid]]<=when){
sol=mid+1;
low=mid+1;
}else{
high=mid-1;
}
}
return sol;
}
int delta[N];
vector<pair<int, int>> factorize(int n){
vector<pair<int, int>> sol;
for(int d=2;d*d<=n;d++){
int e=0;
while(n%d==0) n/=d, e++;
if(e) sol.push_back({d, e});
}
if(n>1){
sol.push_back({n, 1});
}
return sol;
}
int pwmod(int a,int b){
assert(0<=a&&a<mod);
int r=1;
while (b) {
if (b&1) r=r*(ll)a%mod;
a=a*(ll)a%mod;
b/=2;
}
return r;
}
int y;
const int MX=1;
struct T {
int w=1; /// coprime with mod
int e[11];
};
T mlt[N][MX];
void mulup(T&a,T&b){
a.w=a.w*(ll)b.w%mod;
for (int i=0;i<y;i++){
a.e[i]+=b.e[i];
}
}
signed main() {
#ifdef ONLINE_JUDGE
home = 0;
#endif
home=0;
if (home) {
freopen("I_am_iron_man", "r", stdin);
}
else {
ios::sync_with_stdio(0); cin.tie(0);
}
cin>>n>>mod;
vector<pair<int, int>> mod_factors=factorize(mod);
mod_phi=mod;
for (auto &it:mod_factors){
if(mod_phi%it.first==0) mod_phi/=it.first, mod_phi*=(it.first-1);
}
y=(int)mod_factors.size();
for (int i=1;i<n;i++) {
int a, b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
build(1);
for(int i=2;i<=top;i++) lg[i]=1+lg[i/2];
for (int k=1;(1<<k)<=top;k++) {
for(int i=1;i+(1<<k)-1<=top;i++){
rmq[k][i]=min(rmq[k-1][i],rmq[k-1][i+(1<<(k-1))]);
}
}
{
top=0;
for (int d=0;d<=n;d++){
delta[d]=top;
for(auto &i:la[d]){
verts[++top]=i;
pos[i]=top;
}
}
assert(top==n);
}
for (int i=1;i<=n;i++) {
cin>>h[pos[i]];
}
cin>>q;
while(q--){
int type;
cin>>type;
assert(type==1||type==2);
if(type==1){
int x,d,w;
cin>>x>>d>>w;
vector<int> cnt_divi_w(y);
for (int i=0;i<y;i++){
while(w%mod_factors[i].first==0) {
w/=mod_factors[i].first;
cnt_divi_w[i]++;
}
}
int winv=pwmod(w,mod_phi-1);
assert(w*(ll)winv%mod==1);
T t;
T tinv;
t.w=w;
tinv.w=winv;
for (int i=0;i<y;i++){
t.e[i]=cnt_divi_w[i];
tinv.e[i]=-cnt_divi_w[i];
}
int vertex=x,ant;
while (vertex>=1&&d>=0) {
mulup(mlt[vertex][d],t);
if(vertex!=x){
if (d-1>=0){
mulup(mlt[ant][d-1],tinv);
}
}
ant=vertex;
vertex=par[vertex];
d--;
}
}else{
int x,xinit;
cin>>x;
xinit=x;
T cur;
cur.w=1;
for(int i=0;i<y;i++){
cur.e[i]=0;
}
int cur_dist=0;
while (x>=1&&cur_dist<=MX){
for (int i=cur_dist;i<=MX;i++){
mulup(cur,mlt[x][i]);
}
x=par[x];
cur_dist++;
}
x=xinit;
int sol=h[pos[x]];
sol=sol*(ll)cur.w%mod;
for (int i=0;i<y;i++){
if(cur.e[i]) {
sol=sol*(ll)pwmod(mod_factors[i].first,cur.e[i])%mod;
}
}
cout<<sol<<"\n";
}
}
}
Compilation message
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:122:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
122 | freopen("I_am_iron_man", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:195:20: warning: 'ant' may be used uninitialized in this function [-Wmaybe-uninitialized]
195 | int vertex=x,ant;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4097 ms |
19156 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
