Submission #1183989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183989		browntoad	Sprinkler (JOI22_sprinkler)	C++20	3 / 100	4131 ms	778412 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n) 
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const ll maxn = 2e5+5;

int n, mod, q;
int phi;
vector<int> g[maxn];
vector<int> H(maxn);

ll pw(ll a, ll p){
    ll ret = 1;
    while(p > 0){
        if (p & 1){
            ret *= a;
            ret %= mod;
        }
        a *= a;
        a %= mod;
        p >>= 1;
    }
    return ret;
}
ll inv(ll a){
    return pw(a, phi-1);
}

const int mxdis = 40;

int eptr = 0;
int Bv[mxdis+1][10][2*maxn];
int Av[mxdis+1][2*maxn];
int Btot[mxdis+1][10][maxn];
int Atot[mxdis+1][maxn];

// centroid decomposition
vector<bool> isrem(maxn); // removed?
vector<int> preeid[maxn], precent[maxn], dis[maxn]; // eid connecting previous centroid - this centroid, previous centroid. last precent is itself
vector<int> sz(maxn); 


int find_sz(int u, int pre){
    sz[u] = 1;
    for (auto v:g[u]){
        if (v != pre && !isrem[v]) sz[u] += find_sz(v, u);
    }
    return sz[u];
}
int find_centroid(int u, int expsz, int pre){
    for (auto v:g[u]){
        if (!isrem[v] && v != pre && sz[v]*2 > expsz){
            return find_centroid(v, expsz, u);
        }
    }    
    return u;
}

void centupd(int u, int peid, int pecent, int cd, int pre){
    preeid[u].pb(peid);
    precent[u].pb(pecent);
    dis[u].pb(cd);
    for (auto v:g[u]){
        if (!isrem[v] && v != pre){
            centupd(v, peid, pecent, cd+1, u);
        }
    }

}
void decomposition(int u){
    int cent = find_centroid(u, find_sz(u, -1), -1);
    isrem[cent] = 1;
    precent[cent].pb(cent);
    for (auto v:g[cent]){
        if (!isrem[v]){
            centupd(v, eptr++, cent, 1, cent);
            decomposition(v);
        }
    }
}

vector<int> sieve(maxn), prim;
vector<int> specp;

void modify(int U, int D, int W){
    ll A = 1;
    vector<int> B(SZ(specp));
    if (W == 0){
        B[0] = 1;
    }
    else{
        REP1(i, SZ(specp)-1){
            while(W%specp[i] == 0){
                B[i]++;
                W /= specp[i];
            }
        }
        A = W;
    }
    REP(i, SZ(precent[U])){
        int u = precent[U][i]; // centroid id
        if (u == U){
            Atot[D][u] = (Atot[D][u] * A)%mod;
            REP(k, SZ(specp)) Btot[D][k][u] += B[k];
        }
        else{
            int eid = preeid[U][i], dd = D-dis[U][i];
            if (dd < 0) continue;

            Atot[dd][u] = (Atot[dd][u] * A)%mod;
            Av[dd][eid] = (Av[dd][eid] * A)%mod;
            REP(k, SZ(specp)){
                Btot[dd][k][u] += B[k];
                Bv[dd][k][eid] += B[k];
            }
        }
    }

}
int query(int U){
    ll A = 1, Ainv = 1;
    vector<int> B(SZ(specp));
    REP(i, SZ(precent[U])){
        int u = precent[U][i];
        if (u == U){
            FOR(k, 0, mxdis+1){
                A = (A * Atot[k][u])%mod;
                REP(p, SZ(specp)) B[p] += Btot[k][p][u];
            }
        }
        else{
            int eid = preeid[U][i], dd = dis[U][i];
            FOR(k, dd, mxdis+1){
                A = (A * Atot[k][u])%mod;
                Ainv = (Ainv * Av[k][eid])%mod;
                REP(p, SZ(specp)){
                    B[p] += Btot[k][p][u];
                    B[p] -= Bv[k][p][eid];
                }
            }
        }
    }
    if (B[0] > 0) return 0;
    A *= inv(Ainv);
    A %= mod;
    REP1(i, SZ(specp)-1){
        A = (A * pw(specp[i], B[i]) % mod);
    }
    A = (A * H[U])%mod;
    return A;
}

signed main(){
    IOS();
    cin>>n>>mod;
    specp.pb(0);
    int tmod = mod;
    FOR(i, 2, maxn){
        if (!sieve[i]) prim.pb(i);
        for (int j = i+i; j < maxn; j += i) sieve[j] = 1;
    }
    phi = mod;
    for (auto v:prim){
        if (tmod%v == 0){
            while(tmod%v == 0) tmod/=v;
            specp.pb(v);
        }
    }
    if (tmod > 1) specp.pb(tmod);
    for (auto p:specp){
        if (p > 0) phi = ((ll)(p-1) * phi)/p;
    }

    REP(i, mxdis+1){
        REP(j, maxn){
            Atot[i][j] = 1;
        }
        REP(j, 2*maxn){
            Av[i][j] = 1;
        }
    }

    REP(i, n-1){
        int u, v; cin>>u>>v;
        g[u].pb(v); g[v].pb(u);
    }
    REP1(i, n) cin>>H[i];
    decomposition(1);

    cin>>q;
    REP(i, q){
        int t; cin>>t;
        if (t == 1){
            int a, b, c; cin>>a>>b>>c;
            modify(a, b, c);
        }
        else{
            int x; cin>>x;
            cout<<query(x)<<endl;
        }
    }
}
/*
4 7
1 2
2 3
3 4
1
1
1
1

11
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
1 4 10 2
2 1
2 2
2 3
2 4

5 12
1 2
1 3
3 4
1 5
6
1
3
5
3
6
1 2 2 3
1 3 2 3
1 5 2 7
2 3
2 1
2 4
*/

• Subtask 1: 3 / 3
• Subtask 2: 0 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17