树链剖分//模板题
由于存在换根操作
对所有关于节点 u 的修改和查询操作进行分类讨论
若 Root 在 u 的子树中,则不处理 u 所在的 Root 的那颗子树
否则不会有影响
寻找 Root 所在的那颗子树的根可以用倍增求

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string> const int N = 1e5 + ; #define LL long long int topp[N], fa[N], size[N], son[N], deep[N], tree[N], lst[N], rst[N], bef[N], data[N];
int f[N][];
int Tree;
LL W[N << ], F[N << ], S[N << ];
struct Node {
int u, v, nxt;
} G[N << ];
int now, head[N];
int n, m, Root; int opt, T; #define gc getchar() inline int read() {
int x = ; char c = gc;
while(c < '' || c > '') c = gc;
while(c >= '' && c <= '') x = x * + c - '', c = gc;
return x;
} void Add(int u, int v) {G[++ now].v = v; G[now].nxt = head[u]; head[u] = now;} void Dfs_1(int u, int f_, int dep) {
fa[u] = f_, deep[u] = dep, size[u] = ;
for(int i = head[u]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(v == f_) continue;
f[v][] = u;
Dfs_1(v, u, dep + );
size[u] += size[v];
if(size[son[u]] < size[v]) son[u] = v;
}
} void Dfs_2(int u, int tp) {
topp[u] = tp, tree[u] = ++ Tree, bef[Tree] = u, lst[u] = Tree;
if(!son[u]) {
rst[u] = Tree; return ;
}
Dfs_2(son[u], tp);
for(int i = head[u]; ~ i; i = G[i].nxt) {
int v = G[i].v;
if(v != fa[u] && v != son[u]) Dfs_2(v, v);
}
rst[u] = Tree;
} void Before() {
for(int i = ; ( << i) <= n; i ++)
for(int j = ; j <= n; j ++)
if(f[j][i - ]) f[j][i] = f[f[j][i - ]][i - ];
} #define lson jd << 1
#define rson jd << 1 | 1 void Build_tree(int l, int r, int jd) {
S[jd] = (r - l + );
if(l == r) {
W[jd] = data[bef[l]];
return ;
}
int mid = (l + r) >> ;
Build_tree(l, mid, lson);
Build_tree(mid + , r, rson);
W[jd] = W[lson] + W[rson];
} void Pushdown(int jd) {
if(!F[jd]) return ;
F[lson] += F[jd];
F[rson] += F[jd];
W[lson] += (S[lson] * F[jd]);
W[rson] += (S[rson] * F[jd]);
F[jd] = ;
} void Sec_G(int l, int r, int jd, int x, int y, int num) {
if(x <= l && r <= y) {
F[jd] += num;
W[jd] += (S[jd] * num);
return ;
}
Pushdown(jd);
int mid = (l + r) >> ;
if(x <= mid) Sec_G(l, mid, lson, x, y, num);
if(y > mid) Sec_G(mid + , r, rson, x, y, num);
W[jd] = W[lson] + W[rson];
} void Sec_G_imp(int x, int y, int num) {
int tpx = topp[x], tpy = topp[y];
while(tpx != tpy) {
if(deep[tpx] < deep[tpy]) std:: swap(tpx, tpy), std:: swap(x, y);
Sec_G(, n, , tree[tpx], tree[x], num);
x = fa[tpx];
tpx = topp[x];
}
if(deep[x] < deep[y]) std:: swap(x, y);
Sec_G(, n, , tree[y], tree[x], num);
return ;
} inline int Find(int x, int y) {
int dy = deep[y], dx = deep[x];
int del = deep[y] - deep[x] - ;
for(int i = ; ( << i) <= del; i ++)
if(del & ( << i)) y = f[y][i];
return y;
} LL Answer; void Sec_A(int l, int r, int jd, int x, int y) {
if(x <= l && r <= y) {
Answer += W[jd];
return ;
}
Pushdown(jd);
int mid = (l + r) >> ;
if(x <= mid) Sec_A(l, mid, lson, x, y);
if(y > mid) Sec_A(mid + , r, rson, x, y);
} LL Sec_A_imp(int x, int y) {
int tpx = topp[x], tpy = topp[y];
LL ret = ;
while(tpx != tpy) {
if(deep[tpx] < deep[tpy]) std:: swap(tpx, tpy), std:: swap(x, y);
Answer = ;
Sec_A(, n, , tree[tpx], tree[x]);
ret += Answer;
x = fa[tpx];
tpx = topp[x];
}
if(deep[x] < deep[y]) std:: swap(x, y);
Answer = ;
Sec_A(, n, , tree[y], tree[x]);
ret += Answer;
return ret;
} int main() {
Root = ;
n = read();
for(int i = ; i <= n; i ++) head[i] = -;
for(int i = ; i <= n; i ++) data[i] = read();
for(int i = ; i < n; i ++) {
int u = read();
Add(i + , u), Add(u, i + );
}
Dfs_1(, , );
Dfs_2(, );
Build_tree(, n, );
Before();
int t = read();
for(T = ; T <= t; T ++) {
opt = read();
if(opt == ) Root = read();
else if(opt == ) {
int u = read(), v = read(), x = read();
Sec_G_imp(u, v, x);
} else if(opt == ) {
int u = read(), x = read();
if(Root == u) {
Sec_G(, n, , , n, x);
continue;
}
if(lst[u] <= tree[Root] && tree[Root] <= rst[u]) {
Sec_G(, n, , , n, x);
int Use_son = Find(u, Root);
Sec_G(, n, , lst[Use_son], rst[Use_son], -x);
} else Sec_G(, n, , lst[u], rst[u], x);
} else if(opt == ) {
int x = read(), y = read();
printf("%lld\n", Sec_A_imp(x, y));
} else {
int u = read();
if(Root == u) {
Answer = ;
Sec_A(, n, , , n);
printf("%lld\n", Answer);
continue;
}
LL Now_ans = ;
if(lst[u] <= tree[Root] && tree[Root] <= rst[u]) {
Answer = ;
Sec_A(, n, , , n);
Now_ans += Answer;
int Use_son = Find(u, Root);
Answer = ;
Sec_A(, n, , lst[Use_son], rst[Use_son]);
Now_ans -= Answer;
} else {
Answer = ;
Sec_A(, n, , lst[u], rst[u]);
Now_ans += Answer;
}
printf("%lld\n", Now_ans);
}
}
return ;
}

最新文章

  1. cursor中的url整理
  2. Greenplum迁移到配置不同的GP系统
  3. Vehicle’s communication protocol
  4. 对REST的一些理解
  5. 层层递进Struts1(七)详解DispatchAction
  6. response.sendRedirect 传递参数的问题
  7. JavaScript中typeof和instanceof深入详解
  8. properJavaRDP 跑通本地远程桌面
  9. 初识C语言(六)
  10. EasyExcel导入工具(SpringMVC下使用)
  11. ubuntu 系统关键指令
  12. Codeforces Round #367 (Div. 2) D. Vasiliy&#39;s Multiset(01字典树求最大异或值)
  13. idea 断点上面有x
  14. [转]我的数据结构不可能这么可爱!——珂朵莉树(ODT)详解
  15. JS弹出层遮罩,隐藏背景页面滚动条细节优化
  16. (转)C#制作一个消息拦截器
  17. Codeforces Round #243 (Div. 2)——Sereja and Swaps
  18. ios判断设备是iphone还是ipad
  19. iOS二维码扫描的实现(Swift)
  20. SDL封装的系统操作(转载)

热门文章

  1. nginx与PHP编译configure
  2. golang的for循环基本语法
  3. typescript 入门教程三
  4. 转 使用IParameterInspector, IOperationBehavior,Attribute(参数检查器、操作行为接口和标签)扩展WCF操作行为
  5. linux--安全加固脚本
  6. 使用swap扩展内存
  7. js中0.1+0.2 与0.3的对比
  8. [原]Object-Oriented Programming With ANSI-C
  9. RuntimeWarning: DateTimeField AppToken.expire_date received a naive datetime (2019-05-16 16:54:01.144582) while time zone support is active. RuntimeWarning)
  10. TLS握手秘钥套件分析