CF916E Jamie and Tree
题意翻译
有一棵n个节点的有根树，标号为1-n，你需要维护以下三种操作1.给定一个点v，将整颗树的根变为v
2.给定两个点u, v，将lca(u, v)所在的子树都加上x
3.给定一个点v，你需要回答以v所在的子树的权值和
Translated by mangoyang
错误日志： 第一次 \(debug\) 是 \(jump\) 数组第二维开小了； 交了一次错了， 第二次没有特判修改/查询节点等于根的情况； 第三次 \(RE\) 又是数组开销了 。。。空间那么大我倒是把数组卡大点啊啊啊
Solution
树链剖分， 要求换根修改和查询
\(lca(u,v)\) 等于 \(lca(u, v)\ ,lca(u, root)\ ,lca(v, root)\) 里深度最大的点
修改和查询： 分三种情况考虑：- 操作节点为根节点： 直接操作于整棵树
- 根节点在操作节点子树之外： 直接操作即可
- 根节点位于操作节点子树内： 利用容斥（最好画图看看）。设点 \(son\) 为从根节点到操作节点路径上的倒数第二个点，先整棵树更新， 再将 \(son\) 的子树减去更新值即可 （又或者常数较大的先更新整棵树， 反过来减去操作节点的子树， 再更新操作节点这一个点）
Code
#include#include #include #include #include typedef long long LL;using namespace std;LL RD(){ LL out = 0,flag = 1;char c = getchar(); while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();} while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();} return flag * out; }const LL maxn = 200019,INF = 1e9 + 19;LL head[maxn],nume = 1;struct Node{ LL v,dis,nxt; }E[maxn << 2];void add(LL u,LL v,LL dis){ E[++nume].nxt = head[u]; E[nume].v = v; E[nume].dis = dis; head[u] = nume; }LL num, na;LL dep[maxn], size[maxn], fa[maxn], wson[maxn], top[maxn], pos[maxn], ori[maxn], cnt;LL v[maxn];void dfs1(LL id, LL F){ size[id] = 1; for(LL i = head[id];i;i = E[i].nxt){ LL v = E[i].v; if(v == F)continue; dep[v] = dep[id] + 1; fa[v] = id; dfs1(v, id); size[id] += size[v]; if(size[v] > size[wson[id]])wson[id] = v; } }void dfs2(LL id, LL TP){ pos[id] = ++cnt; ori[cnt] = id; top[id] = TP; if(!wson[id])return ; dfs2(wson[id], TP); for(LL i = head[id];i;i = E[i].nxt){ LL v = E[i].v; if(v == fa[id] || v == wson[id])continue; dfs2(v, v); } }#define lid (id << 1)#define rid (id << 1) | 1struct seg_tree{ LL l, r; LL lazy, sum; }tree[maxn << 2];void pushup(LL id){tree[id].sum = tree[lid].sum + tree[rid].sum;}void pushdown(LL id){ if(tree[id].lazy){ LL val = tree[id].lazy; tree[lid].lazy += val; tree[rid].lazy += val; tree[lid].sum += (tree[lid].r - tree[lid].l + 1) * val; tree[rid].sum += (tree[rid].r - tree[rid].l + 1) * val; tree[id].lazy = 0; } }void build(LL id, LL l, LL r){ tree[id].l = l, tree[id].r = r; if(l == r){ tree[id].sum = v[ori[l]]; return ; } LL mid = (l + r) >> 1; build(lid, l, mid), build(rid, mid + 1, r); pushup(id); }void update(LL id, LL val, LL l, LL r){ pushdown(id); if(tree[id].l == l && tree[id].r == r){ tree[id].sum += (tree[id].r - tree[id].l + 1) * val; tree[id].lazy += val; return ; } LL mid = (tree[id].l + tree[id].r) >> 1; if(mid < l)update(rid, val, l, r); else if(mid >= r)update(lid, val, l, r); else update(lid, val, l, mid), update(rid, val, mid + 1, r); pushup(id); }LL query(LL id, LL l ,LL r){ pushdown(id); if(tree[id].l == l && tree[id].r == r){ return tree[id].sum; } LL mid = (tree[id].l + tree[id].r) >> 1; if(mid < l)return query(rid, l, r); else if(mid >= r)return query(lid, l, r); else return query(lid, l, mid) + query(rid, mid + 1, r); }LL root = 1, jump[maxn][25];void get_jump(){ for(LL i = 1;i <= num;i++)jump[i][0] = fa[i]; for(LL i = 1;i <= 19;i++){ for(LL j = 1;j <= num;j++){ jump[j][i] = jump[jump[j][i - 1]][i - 1]; } } }LL LCA(LL x, LL y){ if(dep[x] < dep[y])swap(x, y); for(LL i = 19;i >= 0;i--)if(dep[jump[x][i]] >= dep[y])x = jump[x][i]; if(x == y)return x; for(LL i = 19;i >= 0;i--)if(jump[x][i] != jump[y][i])x = jump[x][i], y = jump[y][i]; return jump[x][0]; }LL real_LCA(LL x, LL y){ LL lca1 = LCA(x, y), lca2 = LCA(x, root), lca3 = LCA(y, root); LL lca = dep[lca1] > dep[lca2] ? lca1 : lca2; return dep[lca] > dep[lca3] ? lca : lca3; }LL son_LCA(LL x, LL y = root){ if(dep[x] >= dep[y])return -1; for(LL i = 19;i >= 0;i--)if(dep[jump[y][i]] >= dep[x] + 1)y = jump[y][i]; if(fa[y] == x)return y; return -1; }void change_root(){root = RD();}void uprange(){ LL x = RD(), y = RD(), val = RD(); LL lca = real_LCA(x, y); if(lca == root){update(1, val, pos[1], pos[1] + size[1] - 1);return ;} LL son = son_LCA(lca); if(son == -1){update(1, val, pos[lca], pos[lca] + size[lca] - 1);return ;} update(1, val, pos[1], pos[1] + size[1] - 1); update(1,-val, pos[son], pos[son] + size[son] - 1); }void get_sum(){ LL x = RD(); if(x == root){printf("%lld\n", query(1, pos[1], pos[1] + size[1] - 1));return ;} LL son = son_LCA(x); if(son == -1){printf("%lld\n", query(1, pos[x], pos[x] + size[x] - 1));return ;} printf("%lld\n", query(1, pos[1], pos[1] + size[1] - 1) - query(1, pos[son], pos[son] + size[son] - 1)); }int main(){ num = RD();na = RD(); for(LL i = 1;i <= num;i++)v[i] = RD(); for(LL i = 1;i <= num - 1;i++){ LL u = RD(), v = RD(); add(u, v, 1), add(v, u, 1); } dep[1] = 1; dfs1(1, -1), dfs2(1, 1); build(1, 1, num); get_jump(); for(LL i = 1;i <= na;i++){ LL cmd = RD(); if(cmd == 1)change_root(); else if(cmd == 2)uprange(); else get_sum(); } return 0; }