一、题目链接
二、题意
给定一棵树，有四种操作：
$1\ u\ v\ x$：把节点$u$到$v$路径上的所有点的权值乘以$x$；
$2\ u\ v\ x$：把节点$u$到$v$路径上的所有点的权值加上$x$；
$3\ u\ v$：把节点$u$到$v$路径上的所有点的权值取反(~操作)；
$4\ u\ v$：查询节点$u$到$v$路径上的所有点的权值和；
所有操作都需要$mod\ 2^{64}$。
三、思路
操作1、2和4是很裸的树链剖分。关键是操作3。这里有个小技巧：对任意一个数字$x$取反，都等于$-(x+1)$。对于此题的$unsigned\ long\ long$类型，同样适用($-1$就是$1111\cdots1111_{(2)}=2^{64}-1$)。明白这个以后，取反操作可以变成加法和乘法。
然后要注意的是，线段树的区间加和区间乘的顺序问题，这里也有个技巧：如果区间$[l,r]$之前的和是$sum$，这个区间先加了一个$x$，再乘了一个$y$，那么可以变成$sum*y+x*y$。即让这个区间先乘一个$y$，再加上$x*y$。这样就可以保证以先乘后加的顺序不出问题了。
然后这题就愉快地AC了。
结论：对任意一个数$x$取反，无论这个数的类型是什么($int,unsigned\ int,long\ long,unsigned\ long\ long$都可以)，都等于$-(x+1)$。
四、代码
#includeusing namespace std;#define MAXN 100010typedef unsigned long long ULL;struct edge { int to, next; edge(int to = 0, int next = 0): to(to), next(next) {}} es[MAXN * 2];int head[MAXN], ecnt;int f[MAXN], deep[MAXN], siz[MAXN], zson[MAXN], top[MAXN], o2n[MAXN], dfscnt;int n, q;ULL a[MAXN];namespace st { struct node { ULL sum, slazy, plazy; node(ULL a1 = 0, ULL a2 = 0, ULL a3 = 0): sum(a1), slazy(a2), plazy(a3) {} } ns[MAXN * 4]; void init() { for(int i = 0, t = 4 * n + 5; i < t; ++i)ns[i] = node(0, 0, 1); } void pushdown(int rt, int l, int r) { int lch = rt << 1, rch = rt << 1 | 1, mid = (l + r) >> 1; if(ns[rt].plazy != 1 || ns[rt].plazy != 0) { ns[lch].sum = ns[lch].sum * ns[rt].plazy + (mid - l + 1) * ns[rt].slazy; ns[rch].sum = ns[rch].sum * ns[rt].plazy + (r - mid) * ns[rt].slazy; ns[lch].plazy *= ns[rt].plazy; ns[rch].plazy *= ns[rt].plazy; ns[lch].slazy = ns[lch].slazy * ns[rt].plazy + ns[rt].slazy; ns[rch].slazy = ns[rch].slazy * ns[rt].plazy + ns[rt].slazy; ns[rt].plazy = 1, ns[rt].slazy = 0; } } void update(int ul, int ur, ULL x, int type, int rt = 1, int l = 1, int r = n) { if(l > ur || r < ul)return; if(l >= ul && r <= ur) { if(type == 2)ns[rt].sum += x * ULL(r - l + 1), ns[rt].slazy += x; else ns[rt].sum *= x, ns[rt].plazy *= x, ns[rt].slazy *= x; return; } pushdown(rt, l, r); int mid = (l + r) >> 1; if(ul <= mid)update(ul, ur, x, type, rt << 1, l, mid); if(ur > mid)update(ul, ur, x, type, rt << 1 | 1, mid + 1, r); ns[rt].sum = ns[rt << 1].sum + ns[rt << 1 | 1].sum; } ULL query(int ql, int qr, int rt = 1, int l = 1, int r = n) { if(l > qr || r < ql)return 0LL; if(l >= ql && r <= qr)return ns[rt].sum; pushdown(rt, l, r); int mid = (l + r) >> 1; ULL res = 0; if(ql <= mid)res += query(ql, qr, rt << 1, l, mid); if(qr > mid)res += query(ql, qr, rt << 1 | 1, mid + 1, r); return res; }};void add(int from, int to) { es[++ecnt] = edge(to, head[from]), head[from] = ecnt;}void init() { memset(head, 0, sizeof(head[0]) * (n + 3)); ecnt = 0; memset(zson, 0, sizeof(zson[0]) * (n + 3)); dfscnt = 0; st::init();}void dfs1(int root, int par) { deep[root] = deep[par] + 1, f[root] = par, siz[root] = 1; int ms = 0; for(int i = head[root]; i; i = es[i].next) { int to = es[i].to; if(to != par) { dfs1(to, root); siz[root] += siz[to]; if(ms < siz[to]) { ms = siz[to], zson[root] = to; } } }}void dfs2(int root, int par, int tp) { top[root] = tp, o2n[root] = ++dfscnt; st::update(dfscnt, dfscnt, a[root], 2); if(!zson[root])return; dfs2(zson[root], root, tp); for(int i = head[root]; i; i = es[i].next) { int to = es[i].to; if(to != par && to != zson[root]) { dfs2(to, root, to); } }}void update(int u, int v, ULL x, int type) { int tu = top[u], tv = top[v]; while(tu != tv) { if(deep[tu] >= deep[tv]) { st::update(o2n[tu], o2n[u], x, type); u = f[tu], tu = top[u]; } else { st::update(o2n[tv], o2n[v], x, type); v = f[tv], tv = top[v]; } } if(o2n[u] <= o2n[v])st::update(o2n[u], o2n[v], x, type); else st::update(o2n[v], o2n[u], x, type);}ULL query(int u, int v) { int tu = top[u], tv = top[v]; ULL res = 0; while(tu != tv) { if(deep[tu] >= deep[tv]) { res += st::query(o2n[tu], o2n[u]); u = f[tu], tu = top[u]; } else { res += st::query(o2n[tv], o2n[v]); v = f[tv], tv = top[v]; } } if(o2n[u] <= o2n[v])res += st::query(o2n[u], o2n[v]); else res += st::query(o2n[v], o2n[u]); return res;}int main() {// freopen("e.in","r",stdin); int fa, op, u, v; ULL x; while(~scanf("%d", &n)) { init(); for(int i = 2; i <= n; ++i) { scanf("%d", &fa); add(fa, i), add(i, fa); } dfs1(1, 0); dfs2(1, 0, 1); scanf("%d", &q); while(q--) { scanf("%d", &op); if(op == 1) { scanf("%d%d%llu", &u, &v, &x); update(u, v, x, 1); } else if(op == 2) { scanf("%d%d%llu", &u, &v, &x); update(u, v, x, 2); } else if(op == 3) { scanf("%d%d", &u, &v); update(u, v, 1, 2); update(u, v, -1, 1); } else { scanf("%d%d", &u, &v); ULL res = query(u, v); printf("%llu\n", res); } } } return 0;}