Submission #1141132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141132		denislav	Sprinkler (JOI22_sprinkler)	C++20	38 / 100	4104 ms	340664 KiB

sprinkler

# include <iostream>
# include <vector>
# include <queue>
using namespace std;

const int MAX=2e5+11;

int n,q;
long long bgn[MAX],MOD;
vector<int> adj[MAX];

void read()
{
    cin>>n>>MOD;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i=1;i<=n;i++) cin>>bgn[i];
}

int ct;
int up[MAX];
pair<int,int> bord[MAX];
int id[MAX];

void tree_basics()
{
    for(int i=1;i<=n;i++)
    {
        bord[i]={1e9,0};
        id[i]=-1;
    }

    queue<int> q;
    q.push(1);

    while(q.size()>0)
    {
        int curr=q.front();
        q.pop();

        id[curr]=++ct;
        bord[up[curr]].first=min(bord[up[curr]].first,id[curr]);
        bord[up[curr]].second=max(bord[up[curr]].second,id[curr]);
        for(int nxt: adj[curr])
        {
            if(id[nxt]!=-1) continue;
            up[nxt]=curr;
            q.push(nxt);
        }
    }

    //for(int i=1;i<=n;i++) cout<<i<<":"<<id[i]<<"->"<<bord[i].first<<" "<<bord[i].second<<"\n";
}

struct seg_tree
{
    long long tree[MAX*4];

    void build()
    {
        for(int i=1;i<=n*4;i++) tree[i]=1;
    }

    void update(int pos, long long d, int v=1, int l=1, int r=n)
    {
        if(l==r)
        {
            tree[v]*=d;
            tree[v]%=MOD;
            return ;
        }

        int mid=(l+r)/2;
        if(pos<=mid) update(pos,d,v*2,l,mid);
        else update(pos,d,v*2+1,mid+1,r);

        tree[v]=(tree[v*2]*tree[v*2+1])%MOD;
    }

    long long query(int le, int ri, int v=1, int l=1, int r=n)
    {
        if(ri<l or r<le) return 1;
        if(le<=l and r<=ri) return tree[v];

        int mid=(l+r)/2;
        return (query(le,ri,v*2,l,mid)*query(le,ri,v*2+1,mid+1,r))%MOD;
    }

}tree[41];

long long source[41][MAX];

void update(int u, int power, long long w)
{
    for(int j=0;j<=power;j++)
    {
        source[j][u]*=w;
        source[j][u]%=MOD;
    }

    while(power>=0 and u!=0)
    {
        for(int j=0;j<=power;j++) tree[j].update(id[u],w);
        u=up[u];
        power--;
    }
}

void query(int u)
{
    long long ans=bgn[u];
    ans*=tree[0].query(id[u],id[u]);ans%=MOD;

    int dist=1;
    int last=u;
    u=up[u];

    while(u!=0)
    {
        ans*=source[dist][u];ans%=MOD;

        //if(dist==40) break;
        if(dist==2) break;

        int l=bord[u].first,r=bord[u].second;
        if(l<=id[last]-1) {ans*=tree[dist+1].query(l,id[last]-1);ans%=MOD;}
        if(id[last]+1<=r) {ans*=tree[dist+1].query(id[last]+1,r);ans%=MOD;}

        dist++;
        last=u;
        u=up[u];
    }

    cout<<ans<<"\n";
}

void solve()
{
    for(int i=0;i<=40;i++)
    {
        tree[i].build();
        for(int j=1;j<=n;j++) source[i][j]=1;
    }

    cin>>q;
    while(q--)
    {
        int tp;
        cin>>tp;

        if(tp==1)
        {
            int u,d,w;
            cin>>u>>d>>w;
            update(u,d,w);
        }
        else if(tp==2)
        {
            int u;
            cin>>u;
            query(u);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    read();
    tree_basics();
    solve();

    return 0;
}

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