题解：P9527 [JOIST 2022] 洒水器 / Sprinkler

vanueber · 2025-10-19 23:35:47 · 题解

厉害的一道题。

将无根树变换为以 1 为根。直接做肯定不行，总点数是很多的，但 d\le 40，启示我们将管辖的信息缩小到这个范围。

令 tag_{u,i} 表示 u 的子树内与 u 距离 i 的点需要乘上的值，那么求 u 的权值只用依次往上跳。

接下来考虑修改，发现 tag_{u,i} 描述了一些特定的点集，而要表示的点集长这样：

我们需要用 tag_{u,i} 表示出这个集合即可。

#include <bits/stdc++.h>
#define int long long
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f;
inline int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const int N=200005,D=45;
int n,mod,h[N],fa[N],q;
vint G[N];
void dfs(int u,int f){
    fa[u]=f;
    for(auto v:G[u]){
        if(v==f) continue;
        dfs(v,u);
    }
}
int tag[N][D];//以u为子树，距离恰好为D的节点需要*

signed main(){
    #ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    #endif
    cin>>n>>mod;
    rep(i,1,n-1){
        int u=read(),v=read();
        G[u].push_back(v),G[v].push_back(u);
    }
    rep(i,1,n) rep(j,0,40) tag[i][j]=1;
    dfs(1,0);
    rep(i,1,n) h[i]=read();
    cin>>q;
    while(q--){
        int op=read();
        if(op==1){
            int x=read(),d=read(),w=read();
            while(x&&d>=0){
                tag[x][d]=tag[x][d]*w%mod;
                if(d>=1) tag[x][d-1]=tag[x][d-1]*w%mod;
                if(x==1){
                    rep(i,0,d-2) tag[1][i]=tag[1][i]*w%mod;
                }
                x=fa[x],--d;
            }
        }
        else{
            int x=read(),res=h[x],d=0;
            while(x&&d<=40){
                res=res*tag[x][d]%mod;
                ++d;
                x=fa[x];
            }
            cout<<res<<"\n";
        }
    }
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}