樹鍊剖分+差分
直接區間加顯然是不行的，由于gcd(a,b,c)=gcd(a,a-b,b-c),那麼我們對這些數差分，然後就變成單點修改。原本以為這道題很簡單，沒想到這麼麻煩，就膜了發代碼。
首先我們考慮如何在樹上差分序列，每個節點有很多個兒子，如果把每個兒子都修改一下就gg了，其實我們可以這個樣子，我們隻維護重兒子的差分值，但是如果從輕兒子爬上來呢？我們就把父親節點單獨取出來做gcd，也就是我們再維護一個原序列的值，每次爬重鍊的時候就把鍊下面最深的點用原序列中的值來求，這樣就可以了。然後還有各種修改，樹狀數組維護原序列比較簡單，就是一個差分序列，但是樹上要注意一些，每次要修改鍊頭和鍊底的重兒子，注意這裡和平常的差分不太一樣，這裡是父親和兒子之間的差分，如果是一條被修改的路徑那麼就抵消，否則就差分，感覺還是挺巧妙的。
view code