【树链剖分】Codechef DGCD_综合

题意：

给出一棵点权树，有M次操作：
1、询问一条路径上的GCD
2、将一段路径上的点权加上d

分析：

如果这题在一个序列上就非常美妙了：
利用辗转相减法： $G C D (a, b) = G C D (a ? b, b)$

所以如果这个问题在一个序列上：
设为 $A_1,A_2,……A_n$
就可以利用差分，变为：
$A_1,A_2-A_1,A_3-A_2,A_4-A-3……A_n-A_{n-1}$
此时的区间修改就变为两次单点修改了。

现在把这个问题转移到树上。。。。就很板了。。。
直接树链剖分，然后对每个链，当成一个序列来做。

然后修改的时候注意一下就行了(笑)。

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 50010
using namespace std;
int dep[MAXN],son[MAXN],fa[MAXN],sz[MAXN],tid[MAXN],rnk[MAXN],top[MAXN],v[MAXN];
int tree[MAXN*4],tag[MAXN*4];
int n,dcnt;
vector<int> a[MAXN];
int gcd(int x,int y){
    if(y==0)return x;return gcd(y,x%y);	
}
void dfs1(int x,int fax){
    dep[x]=dep[fax]+1;fa[x]=fax;son[x]=-1;sz[x]=1;for(int i=0;i<int(a[x].size());i++){
    int u=a[x][i];if(u==fax)continue;dfs1(u,x);	sz[x]+=sz[u];if(son[x]==-1||sz[son[x]]<sz[u])son[x]=u;}
}
void dfs2(int x,int tp){
    top[x]=tp;tid[x]=++dcnt;rnk[dcnt]=x;if(son[x]==-1)return ;dfs2(son[x],tp);for(int i=0;i<a[x].size();i++){
    int u=a[x][i];if(u==fa[x]||u==son[x])continue;dfs2(u,u);	}
}
void build(int l=1,int r=n,int id=1){
    if(l==r){
    if(top[rnk[l]]!=rnk[l])tree[id]=v[fa[rnk[l]]]-v[rnk[l]];	elsetree[id]=v[rnk[l]];return ;}int mid=(l+r)>>1;build(l,mid,id<<1);build(mid+1,r,id<<1|1);tree[id]=gcd(tree[id<<1],tree[id<<1|1]);
}
void change_on_point(int pos,int val,int l=1,int r=n,int id=1){
    if(l==r){
    tree[id]+=val;return ;	}int mid=(l+r)>>1;if(pos<=mid)change_on_point(pos,val,l,mid,id<<1);elsechange_on_point(pos,val,mid+1,r,id<<1|1);tree[id]=gcd(tree[id<<1],tree[id<<1|1]);
}
void change_on_road(int l1,int r1,int val,int l=1,int r=n,int id=1){
    if(l>=l1&&r<=r1){
    tag[id]+=val;return ;	}int mid=(l+r)>>1;if(l1<=mid)change_on_road(l1,r1,val,l,mid,id<<1);if(r1>mid)change_on_road(l1,r1,val,mid+1,r,id<<1|1);
}
int query_on_point(int pos,int l=1,int r=n,int id=1){
    if(l==r)return v[rnk[l]]+tag[id];int mid=(l+r)>>1;if(pos<=mid)return query_on_point(pos,l,mid,id<<1)+tag[id];elsereturn query_on_point(pos,mid+1,r,id<<1|1)+tag[id];	
}
int query_on_road(int l1,int r1,int l=1,int r=n,int id=1){
    if(l>=l1&&r<=r1)return tree[id];int mid=(l+r)>>1;int res1=0,res2=0;if(l1<=mid)res1=query_on_road(l1,r1,l,mid,id<<1);if(r1>mid)res2=query_on_road(l1,r1,mid+1,r,id<<1|1);return gcd(res1,res2);
}
void change_on_tree(int u,int v,int val){
    if(u==v){
    if(top[u]!=u)change_on_point(tid[u],-val);elsechange_on_point(tid[u],val);if(son[u]!=-1)change_on_point(tid[son[u]],val);change_on_road(tid[u],tid[u],val);return ;}while(top[u]!=top[v]){
    if(dep[top[u]]<dep[top[v]])swap(u,v);change_on_road(tid[top[u]],tid[u],val);change_on_point(tid[top[u]],val);if(son[u]!=-1)change_on_point(tid[son[u]],val);u=fa[top[u]];}if(dep[u]>dep[v])swap(u,v);change_on_road(tid[u],tid[v],val);if(top[u]!=u)change_on_point(tid[u],-val);elsechange_on_point(tid[u],val);if(son[v]!=-1)change_on_point(tid[son[v]],val);
}
int query_on_tree(int u,int v){
    if(u==v)return query_on_point(tid[u]);int res=0;while(top[u]!=top[v]){
    if(dep[top[u]]<dep[top[v]])swap(u,v);res=gcd(res,query_on_road(tid[top[u]],tid[u]));u=fa[top[u]];}if(dep[u]>dep[v])swap(u,v);if(u!=v)res=gcd(res,query_on_road(tid[u]+1,tid[v]));res=gcd(res,query_on_point(tid[u]));return res;
}
char s[20];
int main(){
    SF("%d",&n);int x,y,val;for(int i=1;i<n;i++){
    SF("%d%d",&x,&y);x++;y++;a[x].push_back(y);a[y].push_back(x);	}for(int i=1;i<=n;i++)SF("%d",&v[i]);dfs1(1,0);dfs2(1,1);build();int m;SF("%d",&m);for(int i=1;i<=m;i++){
    SF("%s",s);if(s[0]=='F'){
    SF("%d%d",&x,&y);x++,y++;PF("%d\n",abs(query_on_tree(x,y)));}else{
    SF("%d%d%d",&x,&y,&val);x++,y++;change_on_tree(x,y,val);}}
}

顺便提供数据生成器：

#include<cstdio>
#include<cstdlib>
#include<ctime>
#define SF scanf
#define PF printf
#define MAXN 20
#define MAXM 20
#define MAXV 20
using namespace std;
int get_rand(int x){
    return rand()*rand()%x+1;	
}
int main(){
    srand(time(0));int n=MAXN;PF("%d\n",n);	for(int i=1;i<n;i++)PF("%d %d\n",get_rand(i)-1,i);	int m=get_rand(MAXM);for(int i=1;i<=n;i++)PF("%d ",get_rand(MAXV));PF("\n%d\n",m);for(int i=1;i<=m;i++){
    int tag=get_rand(2);if(tag==1)PF("F %d %d\n",get_rand(n)-1,get_rand(n)-1);elsePF("C %d %d %d\n",get_rand(n)-1,get_rand(n)-1,get_rand(MAXV));}
}