树链剖分+差分
直接区间加显然是不行的，由于gcd(a,b,c)=gcd(a,a-b,b-c),那么我们对这些数差分，然后就变成单点修改。原本以为这道题很简单，没想到这么麻烦，就膜了发代码。
首先我们考虑如何在树上差分序列，每个节点有很多个儿子，如果把每个儿子都修改一下就GG了，其实我们可以这个样子，我们只维护重儿子的差分值，但是如果从轻儿子爬上来呢？我们就把父亲节点单独取出来做gcd，也就是我们再维护一个原序列的值，每次爬重链的时候就把链下面最深的点用原序列中的值来求，这样就可以了。然后还有各种修改，树状数组维护原序列比较简单，就是一个差分序列，但是树上要注意一些，每次要修改链头和链底的重儿子，注意这里和平常的差分不太一样，这里是父亲和儿子之间的差分，如果是一条被修改的路径那么就抵消，否则就差分，感觉还是挺巧妙的。
#include<bits/stdc++.h> using namespace std; const int N = 5e4 + 5; inline int rd() { int x = 0, f = 1; char c = getchar(); 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; } int n, m, cnt, dfs_clock; int head[N], a[N], fa[N], dfn[N], top[N], son[N], dep[N], size[N]; struct edge { int nxt, to; } e[N << 1]; int gcd(int a, int b) { return !b ? a : gcd(b, a % b); } void link(int u, int v) { e[++cnt].nxt = head[u]; head[u] = cnt; e[cnt].to = v; } void dfs(int u, int last) { size[u] = 1; for(int i = head[u]; i; i = e[i].nxt) if(e[i].to != last) { dep[e[i].to] = dep[u] + 1; fa[e[i].to] = u; dfs(e[i].to, u); size[u] += size[e[i].to]; if(size[e[i].to] > size[son[u]]) son[u] = e[i].to; } } void dfs(int u, int last, int anc) { dfn[u] = ++dfs_clock; top[u] = anc; if(son[u]) dfs(son[u], u, anc); for(int i = head[u]; i; i = e[i].nxt) if(e[i].to != last && e[i].to != son[u]) dfs(e[i].to, u, e[i].to); } namespace BIT { int tr[N]; void update(int x, int d) { if(!x) return; for(; x <= n; x += x & -x) tr[x] += d; } int query(int x) { int ret = 0; for(; x; x -= x & -x) ret += tr[x]; return ret; } } namespace Segment_Tree { int t[N << 2]; void build(int l, int r, int x) { if(l == r) { t[x] = a[l]; return; } int mid = (l + r) >> 1; build(l, mid, x << 1); build(mid + 1, r, x << 1 | 1); t[x] = gcd(t[x << 1], t[x << 1 | 1]); } void update(int l, int r, int x, int p, int d) { if(l == r) { t[x] += d; return; } int mid = (l + r) >> 1; if(p <= mid) update(l, mid, x << 1, p, d); else update(mid + 1, r, x << 1 | 1, p, d); t[x] = gcd(t[x << 1], t[x << 1 | 1]); } int query(int l, int r, int x, int a, int b) { if(l > b || r < a) return 0; if(l >= a && r <= b) return t[x]; int mid = (l + r) >> 1; return gcd(query(l, mid, x << 1, a, b), query(mid + 1, r, x << 1 | 1, a, b)); } } namespace Operation { int ask(int u, int v) { int ret = 0; while(top[u] != top[v]) { if(dep[top[u]] < dep[top[v]]) swap(u, v); ret = gcd(ret, gcd(Segment_Tree :: query(1, n, 1, dfn[top[u]] + 1, dfn[u]), BIT :: query(dfn[top[u]]))); u = fa[top[u]]; } if(dfn[u] < dfn[v]) swap(u, v); return abs(gcd(ret, gcd(Segment_Tree :: query(1, n, 1, dfn[v] + 1, dfn[u]), BIT :: query(dfn[v])))); } void change(int u, int v, int d) { while(top[u] != top[v]) { if(dep[top[u]] < dep[top[v]]) swap(u, v); Segment_Tree :: update(1, n, 1, dfn[top[u]], -d); if(son[u]) Segment_Tree :: update(1, n, 1, dfn[son[u]], d); BIT :: update(dfn[top[u]], d); BIT :: update(dfn[u] + 1, -d); u = fa[top[u]]; } if(dfn[u] < dfn[v]) swap(u, v); Segment_Tree :: update(1, n, 1, dfn[v], -d); if(son[u]) Segment_Tree :: update(1, n, 1, dfn[son[u]], d); BIT :: update(dfn[v], d); BIT :: update(dfn[u] + 1, -d); } } int main() { n = rd(); for(int i = 1; i < n; ++i) { int u = rd() + 1, v = rd() + 1; link(u, v); link(v, u); } dfs(1, 0); dfs(1, 0, 1); for(int i = 1; i <= n; ++i) { a[dfn[i]] = rd(); BIT :: update(dfn[i], a[dfn[i]]); BIT :: update(dfn[i] + 1, -a[dfn[i]]); } for(int i = n; i; --i) a[i] = a[i - 1] - a[i]; Segment_Tree :: build(1, n, 1); m = rd(); while(m--) { char s[2]; scanf("%s", s); int u = rd() + 1, v = rd() + 1, d; if(s[0] == 'F') printf("%d ", Operation :: ask(u, v)); if(s[0] == 'C') { d = rd(); Operation :: change(u, v, d); } } return 0; }