洛谷p3384 【模板】树链剖分错误记录
首先感谢\(lfd\)在课上调了出来\(Orz\)
\(1\).以后少写全局变量
\(2\).线段树递归的时候最好把左右区间一起传
\(3\).写\(dfs\)的时候不要写错名字
\(4\).使用线段树的操作的时候才要用到\(dfs\)序
\(5\).需要开一个数组来记录在\(dfs\)序下的节点是什么也方便线段树的赋值
\(6\).注意\(down\)函数内怎样更新
\(7\).在查询的时候并不需要向上更新
由于\(yxj\)看了\(lfd\)敲的树链剖分感觉压完行之后非常的好看，由此\(yxj\)也踏上了疯狂压行的不归路
Code：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson k << 1
#define rson k << 1 | 1
using namespace std;
const int N = 1e5+7;
int n, m, R, p, dfn[N], top[N], son[N], dep[N], fa[N], siz[N], tot, head[N << 1], cnt, num, x, y, z, w[N], l, r, ans, pre[N];
struct node {int l, r, f, w;}tr[N << 2];
struct Node {int nxt, to;}e[N << 1];
int read() {
int s = 0, w = 1;
char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') w = -1; ch = getchar();}
while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
void build(int k, int l, int r) {
tr[k].l = l, tr[k].r = r;
if(l == r) {tr[k].w = w[pre[l]]; return;}
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
tr[k].w = (tr[lson].w + tr[rson].w) % p;
}
void add(int x, int y) {
e[++cnt].nxt = head[x];
e[cnt].to = y;
head[x] = cnt;
}
void dfs(int x) {
siz[x] = 1;
dep[x] = dep[fa[x]] + 1;
for(int i = head[x]; i; i = e[i].nxt) {
if(e[i].to == fa[x]) continue;
fa[e[i].to] = x, dfs(e[i].to), siz[x] += siz[e[i].to];
if(siz[e[i].to] > siz[son[x]]) son[x] = e[i].to;
}
}
void dfs1(int x) {
dfn[x] = ++tot; pre[tot] = x;
if(!top[x]) top[x] = x;
if(son[x]) top[son[x]] = top[x], dfs1(son[x]);
for(int i = head[x]; i; i = e[i].nxt)
if(e[i].to != fa[x] && e[i].to != son[x]) dfs1(e[i].to);
}
void down(int k) {
tr[lson].f += tr[k].f; tr[rson].f += tr[k].f;
tr[lson].w += (tr[lson].r - tr[lson].l + 1) * tr[k].f;
tr[rson].w += (tr[rson].r - tr[rson].l + 1) * tr[k].f;
tr[k].f = 0;
}
void change_query(int k) {
if(tr[k].l >= l && tr[k].r <= r) {tr[k].w += (tr[k].r - tr[k].l + 1) * z;tr[k].f += z; return;}
if(tr[k].f) down(k);
int mid = (tr[k].l + tr[k].r) >> 1;
if(l <= mid) change_query(lson);
if(r > mid) change_query(rson);
tr[k].w = (tr[lson].w + tr[rson].w) % p;
}
void work(int x, int y) {
z %= p;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
l = dfn[top[x]], r = dfn[x], change_query(1);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
l = dfn[x], r = dfn[y]; change_query(1);
}
void ask_query(int k) {
if(tr[k].l >= l && tr[k].r <= r) {ans = (ans + tr[k].w) % p; return;}
if(tr[k].f) down(k);
int mid = (tr[k].l + tr[k].r) >> 1;
if(l <= mid) ask_query(lson);
if(r > mid) ask_query(rson);
tr[k].w = (tr[lson].w + tr[rson].w) % p;
}
void work1(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
l = dfn[top[x]], r = dfn[x]; ask_query(1);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
l = dfn[x]; r = dfn[y]; ask_query(1);
}
int main() {
n = read(), m = read(), R = read(), p = read();
for(int i = 1; i <= n; i++) w[i] = read();
for(int i = 1; i < n; i++) x = read(), y = read(), add(x, y), add(y, x);
dfs(R); dfs1(R); build(1, 1, n);
while(m--) {
num = read();
if(num == 1) cin >> x >> y >> z, work(x, y);
if(num == 2) ans = 0, cin >> x >> y, work1(x, y), cout << ans << endl;
if(num == 3) cin >> x >> z, l = dfn[x], r = dfn[x] + siz[x] - 1, change_query(1);
if(num == 4) ans = 0, cin >> x, l = dfn[x], r = dfn[x] + siz[x] - 1, ask_query(1), cout << ans << endl;
}
return 0;
}
谢谢收看，祝身体健康！