倍增前缀和

前置知识$倍增$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})$$\\$

题目内容

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

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

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

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

输入描述

​ 第一行输入四个整数$n,q,x,y(1≤n,q≤2×10^5,-10^6≤x,y ≤10^6)$代表图上点的数量、询问的次数、规则中金币的增加量。 ​ 第二行输入$n$个整数$Next_1,Next_z,...,Next_n(1≤ Next_i≤n)$表示第$i$个节点下一步的位置。 ​ 第三行输入$n$个整数$a_1,a_2,...,a_n(1≤a_i≤10^6)$,表示第$i$个节点的权值。 ​ 此后$q$行，每行输入两个整数$u,k(1≤u≤n,1≤k≤10^9)$ 代表一次询问的起始点和步数限制。

输出描述

对于每一次询问，在一行上输出一个整数，代表最多能获得的金币数量。

样例1

输入

4 5 -2 3
2 3 4 1
5 10 3 2
1 1
1 2
1 4
2 4
2 7

输出

0
1
4
6
8

说明

该样例如下图所示：

●对于第一次询问，走一步会扣除$2$金币，但是可以选择站在原地不走; ●对于第二次询问，走一步时金币数量减至$-2$，走两步金币数量变更为$-2+3=1$。

​

样例2

输入

4 4 2 -1
2 3 1 4
1 2 3 1000000
1 3
3 3
2 2
4 1000000

输出

4
3