题目内容

​ 小塔正在一张有向但定连通的图上玩游戏。这张图包含$n$个点，第$i$个点的权值为$a$，当小美从$i$移动到 $Next_i$时，游戏规则如下:

• 如果$aNeat_i>ai$，小美的金币将增加$x$;

• 如果$aNext_i≤ai$，小美的金币将增加$y$。

  小塔会提出$q$次询问，每个询问从某个点$u$出发，移动不超过$k$步，最多能获得多少金币。

倍增前缀和

前置知识$倍增$https://oi-wiki.org/basic/binary-lifting/ $\\$ 题目给出的是一个类似于内向基环树的图，根据对于每个$i,a[Next[i]]$跟$a[i]$关系可以建立一个边权图$\\$假设$x,y$都是正数，那么对于每次询问的最大前缀和都是走完即可,$\\$接下来就是处理负数对结局的影响.类似的我们可以利用倍增的思想额外去维护这个最大前缀和$pre$,前缀和就是$sum$,$f_{(i,j)}$代表第i给点恰好走$2^j$步,发现对于任意的区间$l,r$,$f_{(l+r).sum}$$=f_{l.sum}+f_{r.sum}$ 而最大前缀和有两种情况取$max$,从左边的序列 $l$ 贡献 $f_{(l+r).pre}=max($$f_{(l+r).pre},f_{l.pre})$和从右边的序列$r$ 贡献，因为必须是前缀需要加上左边序列的元素和 $f_{(l+r).pre}=max$$(f_{l.sum}+$$f_{r.pre},f_{(l+r).pre})$$\\$ 接下来就可以在倍增数组上维护$f_{(i,j)}$了$\\$

$f_{(i+j).sum}=$$f_{(i,j-1).sum}+f_{(f_{(i,j-1)},j-1).sum}$$\\$ $f_{(i+j).pre}=max(f_{(i+j).pre},f_{(i,j-1).pre})$$\\$