树链剖分+差分
直接区间加显然是不行的，由于gcd(a,b,c)=gcd(a,a-b,b-c),那么我们对这些数差分，然后就变成单点修改。原本以为这道题很简单，没想到这么麻烦，就膜了发代码。
首先我们考虑如何在树上差分序列，每个节点有很多个儿子，如果把每个儿子都修改一下就gg了，其实我们可以这个样子，我们只维护重儿子的差分值，但是如果从轻儿子爬上来呢？我们就把父亲节点单独取出来做gcd，也就是我们再维护一个原序列的值，每次爬重链的时候就把链下面最深的点用原序列中的值来求，这样就可以了。然后还有各种修改，树状数组维护原序列比较简单，就是一个差分序列，但是树上要注意一些，每次要修改链头和链底的重儿子，注意这里和平常的差分不太一样，这里是父亲和儿子之间的差分，如果是一条被修改的路径那么就抵消，否则就差分，感觉还是挺巧妙的。
view code