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

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(nqd)O(nqd)O(nqd)。代码#includebits/stdc.husingnamespacestd;typedeflonglongll;intn,mod;//节点数量及模数vectorintG[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){//修改intxX;while(d0x){tag[x][d]tag[x][d]*val%mod;//修改tag[y][d-(dep[x]-dep[y])]if(d-10)tag[x][d-1]tag[x][d-1]*val%mod;//修改tag[y][d-(dep[x]-dep[y])-1]if(!fa[x])for(inti0;id-2;i)tag[x][i]tag[x][i]*val%mod;//特判根节点的情况xfa[x];//往上跳d--;}}llquery(intx){//查询ll ansh[x];for(inti0;i40x;i){//往上跳40个祖先ansans*tag[x][i]%mod;//记录当前祖先对x的标记xfa[x];//往上跳}returnans;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cinnmod;for(inti1,x,y;in;i){cinxy;G[x].push_back(y);G[y].push_back(x);}dfs(1,0);for(inti1;in;i)cinh[i];for(inti1;in;i)for(intj0;j40;j)tag[i][j]1;//记得初始化为1intQ;cinQ;while(Q--){intop;cinop;if(op1){intx,d,v;cinxdv;solve(x,d,v);}else{intx;cinx;coutquery(x)\n;}}return0;}