- Time limit
210 ms
Code length Limit //内存限制也不说一下，真是的……
50000 BOS
LinuxLanguage limit
C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FSAuthor
yellow_agonyTester
laycurseTags
hard, heavy-light, july12, number-theory, yellow_agony
感想
树上动态gcd的第三题也好了。
- [x] BZOJ 2257 [JSOI2009]瓶子和燃料
- [x] BZOJ 5028 小z的加油站
- [x] CodeChef DGCD Dynamic GCD
解题思路
树剖套线段树。线段树维护区间gcd见 小z的加油站 。
另外，注意这题所有点的下标从0开始。
源代码
#include<stdio.h>
#include<algorithm>
const int MAXN=5e5+5;
int n,m;
struct Edge{
int nxt,to;
}e[MAXN<<1];
int cnt=1,head[MAXN];
inline void add(int u,int v)
{
e[cnt]={head[u],v};
head[u]=cnt++;
e[cnt]={head[v],u};
head[v]=cnt++;
}
struct Tree{
int w;
int fa,dep,sz,wson;
int top,id;
}t[MAXN];
void dfs1(int u,int fa)
{
t[u].fa=fa;
t[u].dep=t[fa].dep+1;
t[u].sz=1;
int maxn=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa) continue;
dfs1(v,u);
int temp=t[v].sz;
t[u].sz+=temp;
if(temp>maxn)
{
t[u].wson=v;
maxn=temp;
}
}
}
int id=1;
int a[MAXN];
void dfs2(int u,int top)
{
t[u].top=top;
t[u].id=id;
a[id]=t[u].w;
id++;
if(t[u].sz==1) return;
dfs2(t[u].wson,top);
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==t[u].fa||v==t[u].wson) continue;
dfs2(v,v);
}
}
int gcd(int a,int b)
{
if(a<0) a=-a;
if(b<0) b=-b;
return b?gcd(b,a%b):a;
}
struct Segtree{
int sum,g;//差分后的sum和gcd
}s[MAXN<<2];
inline void pushup(int x)
{
s[x]={s[x<<1].sum+s[x<<1|1].sum,gcd(s[x<<1].g,s[x<<1|1].g)};
}
void build(int x,int l,int r)//建树前的差分交给主函数
{
if(l==r)
{
s[x]={a[l],a[l]};
return;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
}
void update(int x,int l,int r,int pos,int k)//单点修改,增加k
{
if(l==r)
{
s[x].sum+=k;
s[x].g+=k;
return;
}
int mid=l+r>>1;
if(pos<=mid) update(x<<1,l,mid,pos,k);
else update(x<<1|1,mid+1,r,pos,k);
pushup(x);
}
int quegcd(int x,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)
return s[x].g;
int mid=l+r>>1;
if(qr<=mid)
return quegcd(x<<1,l,mid,ql,qr);
else if(ql>mid) return quegcd(x<<1|1,mid+1,r,ql,qr);
else return gcd(quegcd(x<<1,l,mid,ql,qr) , quegcd(x<<1|1,mid+1,r,ql,qr));
}
int quesum(int x,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)
return s[x].sum;
int mid=l+r>>1;
if(qr<=mid)
return quesum(x<<1,l,mid,ql,qr);
else if(ql>mid) return quesum(x<<1|1,mid+1,r,ql,qr);
else return quesum(x<<1,l,mid,ql,qr) + quesum(x<<1|1,mid+1,r,ql,qr);
}
int optf(int u,int v)
{
int ans=0,l,r,temp;
while(t[u].top!=t[v].top)
{
if(t[t[u].top].dep<t[t[v].top].dep) std::swap(u,v);
l=t[t[u].top].id;
r=t[u].id;
temp=quesum(1,1,n,1,l);
if(l!=r) temp=gcd(quegcd(1,1,n,l+1,r),temp);
if(!ans) ans=temp;
else ans=gcd(temp,ans);
u=t[t[u].top].fa;
}
if(t[u].id>t[v].id) std::swap(u,v);
l=t[u].id,r=t[v].id;
temp=quesum(1,1,n,1,l);
if(l!=r) temp=gcd(quegcd(1,1,n,l+1,r),temp);
if(!ans) ans=temp;
else ans=gcd(temp,ans);
return ans;
}
void optc(int u,int v,int d)
{
int l,r;
while(t[u].top!=t[v].top)
{
if(t[t[u].top].dep<t[t[v].top].dep) std::swap(u,v);
l=t[t[u].top].id;
r=t[u].id;
update(1,1,n,l,d);
if(r<n) update(1,1,n,r+1,-d);
u=t[t[u].top].fa;
}
if(t[u].id>t[v].id) std::swap(u,v);
l=t[u].id,r=t[v].id;
update(1,1,n,l,d);
if(r<n) update(1,1,n,r+1,-d);
}
int main()
{
freopen("test.in","r",stdin);
scanf("%d",&n);
for(int i=1,u,v;i<n;i++)
{
scanf("%d%d",&u,&v);
u++,v++;//下标全部增加1
add(u,v);
}
for(int i=1;i<=n;i++)
scanf("%d",&t[i].w);
dfs1(1,0);
dfs2(1,1);
for(int i=n;i>1;i--) a[i]-=a[i-1];
build(1,1,n);
scanf("%d",&m);
while(m--)
{
char opt[3];
int u,v,d;
scanf("%s%d%d",opt,&u,&v);
u++,v++;//下标全部增加1
if(opt[0]=='F')
{
printf("%d\n",optf(u,v));
}
else
{
scanf("%d",&d);
optc(u,v,d);
}
}
return 0;
}