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

注意力惊人

思路

首先，我们注意到Dk≤40D_k\le40Dk​≤40，所以考虑暴力一些的解法。

每次直接遍历所有相邻的点肯定是不行的，但我们注意到与每个节点距离不超过DkD_kDk​的祖先至多有DkD_kDk​个，所以考虑对祖先进行操作。

考虑操作一个点会对哪些点产生影响。

首先肯定会对子树内的点产生影响，设tagx,itag_{x,i}tagx,i​表示对xxx的子树内与xxx距离不超过iii的点的标记，那么直接对tagx,dtag_{x,d}tagx,d​加标记即可。

然后考虑对祖先及其子树内节点的影响。

注：图片及后文的ddd是指当次修改的范围DkD_kDk​。

如图所示，我们只需要对tagfx,d−(depx−depfx)tag_{fx,d-(dep_x-dep_{fx})}tagfx,d−(depx​−depfx​)​乘上WWW并对tagy,d−(depx−depfx)−1tag_{y,d-(dep_x-dep_{fx})-1}tagy,d−(depx​−depfx​)−1​除去WWW即可。

然后每次查询就只需要暴力往上跳祖先累计答案即可。

但是此时有个严峻的问题，就是题目没有保证模数一定与WWW互质，那么我们就无法使用逆元了，而且常数还很大，所以我们要找到一种方法每次修改查询只用乘。

我们注意似乎每次打标记都会打很多重复的标记，考虑修改xxx时，我们每次修改它的祖先，每个祖先yyy（除根节点外）都会被修改两次：一次是给以它为根的子树打上标记，一次是给它父节点去掉x−fxx-fxx−fx的标记。第一次修改的是将tagy,d−(depx−depy)tag_{y,d-(dep_x-dep_y)}tagy,d−(depx​−depy​)​乘WWW，第二次修改的是将tagy,d−(depx−depfx)−1tag_{y,d-(dep_x-dep_{fx})-1}tagy,d−(depx​−depfx​)−1​，即tagy,d−(depx−depy)−2tag_{y,d-(dep_x-dep_y)-2}tagy,d−(depx​−depy​)−2​除WWW，这似乎像一个前缀和形式，于是此时我们去掉重复修改的部分（即[0,d−(depx−depy)−2][0,d-(dep_x-dep_y)-2][0,d−(depx​−depy​)−2]），惊人的发现：此次修改只对yyy的子树中与yyy的距离在[d−(depx−depy)−1,d−(depx−depy)][d-(dep_x-dep_y)-1,d-(dep_x-dep_y)][d−(depx​−depy​)−1,d−(depx​−depy​)]的节点有影响！而且对于xxx本身也是符合这个条件的！

所以我们将tagx,itag_{x,i}tagx,i​的状态改为对xxx的子树内与xxx距离恰好为iii的点的标记，那么每次修改时只需要把xxx及其祖先的tagy,d−(depx−depy)tag_{y,d-(dep_x-dep_y)}tagy,d−(depx​−depy​)​和tagy,d−(depx−depy)−1tag_{y,d-(dep_x-dep_y)-1}tagy,d−(depx​−depy​)−1​改一下即可。需要注意的是，对于根节点，由于它没有父节点，所以他的标记还是距离为[1,d−(depx−depy)][1,d-(dep_x-dep_y)][1,d−(depx​−depy​)]的，所以对于根节点要全部距离≤d−(depx−depy)\le d-(dep_x-dep_y)≤d−(depx​−depy​)的tagrttag_{rt}tagrt​都要修改一遍。

查询就暴力往上跳ddd个祖先yyy，每次记录一下tagy,depx−depytag_{y,dep_x-dep_y}tagy,depx​−depy​​即可。

由于d≤40d\le 40d≤40，每次跳的祖先不超过 40，对于修改的根节点最多只有一个，最多改ddd个距离的标记，所以单次修改和查询的时间复杂度都为O(d)O(d)O(d)，总时间复杂度为O(n+qd)O(n+qd)O(n+qd)。

代码

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intn,mod;//节点数量及模数vector<int>G[200010];ll h[200010]/*初始每个点的高度*/,tag[200010][42]/*题解中的tag数组*/;intfa[200010];//每个点的父节点voiddfs(intx,intxfa){//记录每个节点的父节点fa[x]=xfa;for(inty:G[x])if(y!=xfa){dfs(y,x);}}voidsolve(intX,intd,intval){//修改intx=X;while(d>=0&&x){tag[x][d]=tag[x][d]*val%mod;//修改tag[y][d-(dep[x]-dep[y])]if(d-1>=0)tag[x][d-1]=tag[x][d-1]*val%mod;//修改tag[y][d-(dep[x]-dep[y])-1]if(!fa[x])for(inti=0;i<=d-2;i++)tag[x][i]=tag[x][i]*val%mod;//特判根节点的情况x=fa[x];//往上跳d--;}}llquery(intx){//查询ll ans=h[x];for(inti=0;i<=40&&x;i++){//往上跳40个祖先ans=ans*tag[x][i]%mod;//记录当前祖先对x的标记x=fa[x];//往上跳}returnans;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>mod;for(inti=1,x,y;i<n;i++){cin>>x>>y;G[x].push_back(y);G[y].push_back(x);}dfs(1,0);for(inti=1;i<=n;i++)cin>>h[i];for(inti=1;i<=n;i++)for(intj=0;j<=40;j++)tag[i][j]=1;//记得初始化为1intQ;cin>>Q;while(Q--){intop;cin>>op;if(op==1){intx,d,v;cin>>x>>d>>v;solve(x,d,v);}else{intx;cin>>x;cout<<query(x)<<'\n';}}return0;}