Description

给你一棵有N个结点的数。这N个结点都有一个权值为$C[i]$。
询问你两个结点u、v，在这两个结点的最短路径上，选取两个点i、j，且i靠近结点u，j靠近结点v。让你计算$Max(c[j]-c[i],0)$

Input

输入第一行有一个整数N(1≤n≤50000)
接下来有N 行，每行一个整数Ci(1≤Ci≤50000)
再接下来有N-1 行，每行两个整数x,y(1≤x,y≤50000)，表示x 和y 之间有一条边。
接下来有一个整数M，表示有M 个询问。
然后M 行，每行两个整数，x,y(1≤x,y≤50000)询问$Max(c[j]-c[i],0)$
Output

关于本教程

史上最浅显易懂的Git教程！

为什么要编写这个教程？因为我在学习Git的过程中，买过书，也在网上Google了一堆Git相关的文章和教程，但令人失望的是，这些教程不是难得令人发指，就是简单得一笔带过，或者，只支离破碎地介绍Git的某几个命令，还有直接从Git手册粘贴帮助文档的，总之，初学者很难找到一个由浅入深，学完后能立刻上手的Git教程。

T1:粉刷匠
刚一开始看错题目啦!我认为竖着也可以粉刷,然而并不是,这只是每行粉刷。
因为每一行都是独立的，所以可以分开一行一行染色，随后染色的数目等于T，对于每一行，只需要看这一行用j次粉刷能粉刷的最大数目是多少就可以了。

T2:迷路
在不知道是矩阵乘法时，我是没思路的，当知道是矩阵乘法时只知道边权为1时怎么做。当边权为1时，矩阵乘法一次邻接矩阵，就相当于都走了一步。
因为边权很小在$[1,9]$之间,所以可以将一个点拆成9个点,将他们连接起来。做T次矩阵乘法，就能得到答案。

T3:游戏
将对应关系建成一幅图，发现整个图是有若干个环组成。答案就是求若干个环的大小相加为N时的$\Sigma(LCM)$。到了这一步就不知道怎么做了。因为这里有一个性质

考虑最小公倍数不为1的情况，这它为m。
则m=p1^a1*p2^a2…，而对于一个m，存在一个序列的最小公倍数为m的充要条件是：
p1^a1+p2^a2+….<=n。