uoj #139
2024-08-27 10:50:40
树链剖分//模板题
由于存在换根操作
对所有关于节点 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 ;
}
最新文章
- cursor中的url整理
- Greenplum迁移到配置不同的GP系统
- Vehicle’s communication protocol
- 对REST的一些理解
- 层层递进Struts1(七)详解DispatchAction
- response.sendRedirect 传递参数的问题
- JavaScript中typeof和instanceof深入详解
- properJavaRDP 跑通本地远程桌面
- 初识C语言(六)
- EasyExcel导入工具(SpringMVC下使用)
- ubuntu 系统关键指令
- Codeforces Round #367 (Div. 2) D. Vasiliy&#39;s Multiset(01字典树求最大异或值)
- idea 断点上面有x
- [转]我的数据结构不可能这么可爱!——珂朵莉树(ODT)详解
- JS弹出层遮罩,隐藏背景页面滚动条细节优化
- (转)C#制作一个消息拦截器
- Codeforces Round #243 (Div. 2)——Sereja and Swaps
- ios判断设备是iphone还是ipad
- iOS二维码扫描的实现(Swift)
- SDL封装的系统操作(转载)
热门文章
- nginx与PHP编译configure
- golang的for循环基本语法
- typescript 入门教程三
- 转 使用IParameterInspector, IOperationBehavior,Attribute(参数检查器、操作行为接口和标签)扩展WCF操作行为
- linux--安全加固脚本
- 使用swap扩展内存
- js中0.1+0.2 与0.3的对比
- [原]Object-Oriented Programming With ANSI-C
- RuntimeWarning: DateTimeField AppToken.expire_date received a naive datetime (2019-05-16 16:54:01.144582) while time zone support is active. RuntimeWarning)
- TLS握手秘钥套件分析