小葱将买来的糖放进了冰箱冷藏，但是小葱想吃糖了，小葱希望把自己想吃的糖从冰箱里面拿出来。具体来说，小葱同学的冰箱是一棵\(N\)个点的树，每个点有一颗糖，第\(i\)个点的糖的美味值是\(a_i\)。小葱每次取糖会从根节点出发，指定一个目标节点\(p\)，走到\(p\)点并且把这条路径上的所有糖取走。但小葱不满足只走到\(p\)，所以接下来小葱会继续从\(p\)出发去取其他的糖。但是由于小葱的冰箱的特殊构造，一条边一旦被走过一次就不能再走了，所以小葱要仔细计划如何行动。因此，小葱会有\(M\)次询问，每次询问给定根节点\(q\)和目标节点\(p\)，小葱想知道在这种情况下他能取走的糖果的美味值之和是多少。
对于\(100\%\)的数据，\(1\leq N,M\leq 10^5,1\leq a_i\leq 10^4,1\leq q,p\leq N\)。
世界上没有码量题，只是我自己写不出来的问题
\(dp\) 记录转移前驱并不羞耻，没必要想方设法通过值判断是否为前驱
既然开了 \(10^5\) 就不要考虑常数，判断一个点是否为另一个点的孙子直接 LCA 暴力判常数也能很优秀
倍增跳跃求和还有一种朴素方法为树上前缀和，常数非常优秀(感谢女队教我的)
既然分类讨论不行就不要分类讨论，尽量寻找普遍情况，\(dp\) 式子要适应普遍情况而不是调半天调不出来
数组能开两倍就开两倍！！！数组能开两倍就开两倍！！！数组能开两倍就开两倍！！！