https://vjudge.net/problem/CodeChef-DGCD
https://www.codechef.com/problems/DGCD
题目大意：
给一颗带点权的树，两个操作：
1.将两点间最短路上的点权+d
2.查询两点间最短路上的点权的GCD
显然又是树链剖分，点这里看树链剖分原理。
但是我们发现一个问题，我们虽然可以建立线段树维护GCD，但是没有办法处理区间修改问题。
我们考虑更相减损之术的原理，两数做差后的结果和小数的GCD=原来的GCD。
所以我们在维护单点权值的同时维护相邻点权的差值，则GCD(区间内所有相邻点权差的GCD，区间首位点权)就是我们要查的值。
虽然这么说很简单，但是有很多具体细节，大体比较难解决的比如：
1.修改区间的时候，单点权值要用lazy标记维护，而相邻点权的差值就单点修改两次（注意：有些情况下也可能只有一次）即可。
2.询问的时候，单点权值单点查询即可，相邻点权的差值区间查询，注意区间长度为点数-1，也就是说我们可能会碰到空区间，特判掉。
其余具体操作请看代码。
#include<cstdio>
#include<iostream>
using namespace std;
const int N=;
const int INF=;
/*============================**
*************基本操作************
**============================*/
inline int read(){
int X=,w=;char ch=;
while(ch<''||ch>''){w|=ch=='-';ch=getchar();}
while(ch>=''&&ch<='')X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct node{
int to;
int nxt;
}edge[*N];
struct tree{
int lazy;
int d;
int v;
}t[*N];
int head[N],cnt=,n;
inline void add(int u,int v){
cnt++;
edge[cnt].to=v;
edge[cnt].nxt=head[u];
head[u]=cnt;
return;
}
inline int abs(int x){
return x>?x:-x;
}
int gcd(int x,int y){
return y?gcd(y,x%y):abs(x);
}
int fa[N],dep[N],size[N],son[N],top[N],pos[N],idx[N];
int val[N];
/*============================**
*************树链剖分************
**============================*/
void dfs1(int u){
size[u]=;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa[u])continue;
fa[v]=u;dep[v]=dep[u]+;
dfs1(v);
size[u]+=size[v];
if(!son[u]||size[v]>size[son[u]])son[u]=v;
}
return;
}
int tot;
void dfs2(int u,int anc){
tot++;
pos[u]=tot;
idx[tot]=u;
top[u]=anc;
if(!son[u])return;
dfs2(son[u],anc);
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
return;
}
inline void init(){
dfs1();
top[]=idx[]=pos[]=;
tot=;
dfs2(,);
return;
}
/*============================**
************传递lazy************
**============================*/
inline void pushdown(int a,bool is_leaf){
if(is_leaf){
t[a].v+=t[a].lazy;
}else{
t[a*].lazy+=t[a].lazy;
t[a*+].lazy+=t[a].lazy;
}
t[a].lazy=;
return;
}
/*============================**
*************建树操作************
**============================*/
void build(int a,int l,int r){
if(l==r){
t[a].v=val[idx[l]];
t[a].d=val[idx[l]]-val[idx[l-]];
return;
}
int mid=(l+r)>>;
build(a*,l,mid);
build(a*+,mid+,r);
t[a].d=gcd(t[a*].d,t[a*+].d);
return;
}
/*============================**
*************查询操作************
**============================*/
int point_query(int a,int l,int r,int k){
pushdown(a,(l==r));
if(l==r){
return t[a].v;
}
int mid=(l+r)>>;
if(k<=mid)return point_query(a*,l,mid,k);
return point_query(a*+,mid+,r,k);
}
int range_query(int a,int l,int r,int l1,int r1){
if(l1>r1)return ;
if(r<l1||r1<l)return ;
if(l1<=l&&r<=r1){
return t[a].d;
}
int mid=(l+r)>>;
return gcd(range_query(a*,l,mid,l1,r1),range_query(a*+,mid+,r,l1,r1));
}
int path_query(int u,int v){
if(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){int t=u;u=v;v=t;}
if(top[u]!=u)
return gcd(path_query(fa[top[u]],v),gcd(range_query(,,n,pos[son[top[u]]],pos[u]),point_query(,,n,pos[top[u]])));
return gcd(path_query(fa[top[u]],v),point_query(,,n,pos[top[u]]));
}
if(dep[u]>dep[v]){int t=u;u=v;v=t;}
if(u!=v)
return gcd(point_query(,,n,pos[u]),range_query(,,n,pos[son[u]],pos[v]));
return point_query(,,n,pos[u]);
}
/*============================**
*************修改操作************
**===========================**/
void point_modi(int a,int l,int r,int k,int c){
if(l==r){
t[a].d+=c;
return;
}
int mid=(l+r)>>;
if(k<=mid)point_modi(a*,l,mid,k,c);
else point_modi(a*+,mid+,r,k,c);
t[a].d=gcd(t[a*].d,t[a*+].d);
return;
}
void range_modi(int a,int l,int r,int l1,int r1,int v){
if(r1<l||r<l1)return;
pushdown(a,(l==r));
if(l1<=l&&r<=r1){
t[a].lazy+=v;
return;
}
int mid=(l+r)>>;
range_modi(a*,l,mid,l1,r1,v);
range_modi(a*+,mid+,r,l1,r1,v);
return;
}
void path_modi(int u,int v,int c){
if(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){int t=u;u=v;v=t;}
point_modi(,,n,pos[top[u]],c);
if(son[u]!=u)point_modi(,,n,pos[son[u]],-c);
range_modi(,,n,pos[top[u]],pos[u],c);
path_modi(fa[top[u]],v,c);
return;
}
if(dep[u]>dep[v]){int t=u;u=v;v=t;}
point_modi(,,n,pos[u],c);
if(son[v])point_modi(,,n,pos[son[v]],-c);
range_modi(,,n,pos[u],pos[v],c);
return;
}
/*============================**
*************主程序段************
**============================*/
int main(){
n=read();
for(int i=;i<=n;i++){
int u=read()+;
int v=read()+;
add(u,v);
add(v,u);
}
for(int i=;i<=n;i++)val[i]=read();
init();
build(,,n);
int q=read();
while(q--){
char op=;
while(op!='F'&&op!='C')op=getchar();
if(op=='C'){
int a=read()+;
int b=read()+;
int c=read();
path_modi(a,b,c);
}else{
int a=read()+;
int b=read()+;
printf("%d\n",path_query(a,b));
}
}
return ;
}