Dynamic GCD
题意：一棵树，字词树链加，树链gcd
根据(gcd(a,b)=gcd(a,a-b))
得到(gcd(a_1, a_2, ..., a_i) = gcd(a_1, a_1-a_2, a_2-a_3,...))
同时维护原序列和差分序列就行了
无脑树剖，分成几段。不需要轻儿子的差分值。
注意最后答案取一下绝对值！！！
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 5e4+5;
inline int read() {
char c=getchar(); int x=0,f=1;
while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x*f;
}
#define mid ((l+r)>>1)
#define lc x<<1
#define rc x<<1|1
#define lson lc, l, mid
#define rson rc, mid+1, r
int n, Q, a[N], u, v, d;
char s[5];
struct edge {int v, ne;} e[N<<1];
int cnt, h[N];
inline void ins(int u, int v) {
e[++cnt] = (edge) {v, h[u]}; h[u] = cnt;
e[++cnt] = (edge) {u, h[v]}; h[v] = cnt;
}
int dfn[N], dfc, size[N], mx[N], fa[N], deep[N], top[N];
void dfs(int u) {
size[u] = 1;
for(int i=h[u]; i; i=e[i].ne) {
int v = e[i].v;
if(v == fa[u]) continue;
fa[v] = u; deep[v] = deep[u]+1;
dfs(v);
size[u] += size[v];
if(size[v] > size[mx[u]]) mx[u] = v;
}
}
void dfs(int u, int anc) {
dfn[u] = ++dfc; top[u] = anc;
if(mx[u]) dfs(mx[u], anc);
for(int i=h[u]; i; i=e[i].ne) {
int v = e[i].v;
if(v != fa[u] && v != mx[u]) dfs(v, v);
}
}
namespace t1 {
int c[N];
void add(int p, int v) {for(; p<=n; p+=p&-p) c[p]+=v;}
int que(int p) {int ans=0; for(; p; p-=p&-p) ans+=c[p]; return ans;}
void add(int l, int r, int d) {
add(l, d); add(r+1, -d);
}
}
int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}
namespace t2 {
int t[N<<2];
void build(int x, int l, int r) {
if(l == r) t[x] = a[l];
else {
build(lson); build(rson);
t[x] = gcd(t[lc], t[rc]);
}
}
void add(int x, int l, int r, int p, int v) {
if(l == r) t[x] += v;
else {
if(p <= mid) add(lson, p, v);
else add(rson, p, v);
t[x] = gcd(t[lc], t[rc]);
}
}
int que(int x, int l, int r, int ql, int qr) {
if(ql > qr) return 0;
if(ql <= l && r <= qr) return t[x];
else {
int ans = 0;
if(ql <= mid) ans = gcd(ans, que(lson, ql, qr));
if(mid < qr) ans = gcd(ans, que(rson, ql, qr));
return ans;
}
}
}
int seg_gcd(int x, int y) {
int l = dfn[x], r = dfn[y];
int a = t1::que(l), b = t2::que(1, 1, n, l+1, r);
return gcd(a, b);
}
void quer(int x, int y) {
int ans = 0;
while(top[x] != top[y]) {
if(deep[top[x]] < deep[top[y]]) swap(x, y);
ans = gcd(ans, seg_gcd(top[x], x));
x = fa[top[x]];
}
if(dfn[x] > dfn[y]) swap(x, y);
ans = gcd(ans, seg_gcd(x, y));
if(ans < 0) ans = -ans;
printf("%d
", ans);
}
void seg_add(int x, int y, int d) {
int l = dfn[x], r = dfn[y];
t1::add(l, r, d);
t2::add(1, 1, n, l, -d);
if(mx[y]) t2::add(1, 1, n, dfn[mx[y]], d);
}
void add(int x, int y, int d) { //printf("add %d %d %d
", x, y, d);
while(top[x] != top[y]) {
if(deep[top[x]] < deep[top[y]]) swap(x, y);
seg_add(top[x], x, d);
x = fa[top[x]];
}
if(dfn[x] > dfn[y]) swap(x, y);
seg_add(x, y, d);
}
int main() {
//freopen("in", "r", stdin);
n = read();
for(int i=1; i<n; i++) ins(read()+1, read()+1);
dfs(1); dfs(1, 1);
//for(int i=1; i<=n; i++) printf("look %d %d %d %d
", i, dfn[i], fa[i], mx[i]);
for(int i=1; i<=n; i++) a[dfn[i]] = read();
for(int i=1; i<=n; i++) t1::add(i, i, a[i]);// printf("%d ", a[i]); puts("");
for(int i=n; i>=1; i--) a[i] = a[i-1] - a[i];
t2::build(1, 1, n);
Q = read();
while(Q--) {
scanf("%s", s); u = read()+1; v = read()+1;
//printf("--------------------------%s %d %d
", s, u, v);
if(s[0] == 'F') quer(u, v);
else d = read(), add(u, v, d);
//for(int i=1; i<=n; i++) printf("%d ", t1::que(i)); puts(" val");
//printf("seg_gcd %d
", seg_gcd(1, 2));
}
}