ARC17,18 D

ARC埋めたら増えていくはず

ARC17D
区間addと区間gcd.
横との差をとっとくとaddが来ても更新が2箇所で済む.gcdは合成できるのであとは余裕.
実際のgcdはgcd(a-b,b-c,c-d...)とaのgcdなので,もういっこ実際の値を持っておくsegtreeをつくる(区間add対応の).

ARC18D
行列木定理は多重辺あっても行ける
a[i][i]=degree[i]
a[i][j]=-(i,j)間に生える辺の個数
の余因子を1個取れば良い.