【模板】树链剖分
2025-07-23 10:32:27
发布于:湖南
线段树部分自己完成, tree_spliter
部分看了洛谷题解和OI wiki勉强通过。
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;
int n, m, r, p;
class Segtree{
private:
vector <int> tree, lazytag, left, right;
int n;
void push_up(int u){
tree[u] = (tree[u << 1] + tree[u << 1 | 1]) % p;
}
void push_down(int u){
if(!lazytag[u]) return;
lazytag[u << 1] += lazytag[u];
lazytag[u << 1 | 1] += lazytag[u];
tree[u << 1] += (right[u << 1] - left[u << 1] + 1) * lazytag[u];
tree[u << 1 | 1] += (right[u << 1 | 1] - left[u << 1 | 1] + 1) * lazytag[u];
tree[u << 1] %= p;
tree[u << 1 | 1] %= p;
lazytag[u << 1] %= p;
lazytag[u << 1 | 1] %= p;
lazytag[u] = 0;
}
void build(int u, int l, int r, vector <int> &a){
left[u] = l, right[u] = r;
if(l == r){
tree[u] = a[l];
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid, a);
build(u << 1 | 1, mid + 1, r, a);
push_up(u);
}
void _modify(int u, int l, int r, int val){
if(left[u] >= l && right[u] <= r){
tree[u] += (right[u] - left[u] + 1) * val;
tree[u] %= p;
lazytag[u] += val;
lazytag[u] %= p;
return;
}
push_down(u);
int mid = left[u] + right[u] >> 1;
if(l <= mid) _modify(u << 1, l, r, val);
if(r > mid) _modify(u << 1 | 1, l, r, val);
push_up(u);
}
int _query(int u, int l, int r){
if(left[u] >= l && right[u] <= r) return tree[u];
push_down(u);
int ans = 0;
int mid = left[u] + right[u] >> 1;
if(l <= mid) ans += _query(u << 1, l, r);
if(r > mid) ans += _query(u << 1 | 1, l, r);
return ans % p;
}
public:
Segtree(){}
void init(vector <int> a){
this -> n = a.size() - 1;
tree.resize(a.size() << 2, 0);
left.resize(a.size() << 2, 0);
right.resize(a.size() << 2, 0);
lazytag.resize(a.size() << 2, 0);
build(1, 1, a.size() - 1, a);
}
void modify(int l, int r, int val){
_modify(1, l, r, val % p);
}
int query(int l, int r){
return _query(1, l, r);
}
};
class tree_spliter{
private:
vector <vector <int>> edges;
vector <int> dfn, dep, father, head, rank, son, siz;
Segtree tr;
int n;
void dfs(int cur, int fa){
father[cur] = fa;
siz[cur] = 1;
dep[cur] = dep[fa] + 1;
for(int i:edges[cur]){
if(i == fa) continue;
dfs(i, cur);
siz[cur] += siz[i];
if(siz[son[cur]] < siz[i]) son[cur] = i;
}
}
void dfs2(int cur, int top, int &curdfn){
head[cur] = top;
curdfn++;
dfn[cur] = curdfn;
rank[curdfn] = cur;
if(!son[cur]) return;
dfs2(son[cur], top, curdfn);
for(int i:edges[cur]){
if(i != son[cur] && i != father[cur]) dfs2(i, i, curdfn);
}
}
public:
tree_spliter(){}
void init(int n, vector <int> a, vector <vector <int>> v){
this -> n = n;
edges = v;
dfn.resize(n + 1);
father.resize(n + 1);
son.resize(n + 1);
siz.resize(n + 1);
head.resize(n + 1);
rank.resize(n + 1);
dep.resize(n + 1);
dfs(r, 0);
int curdfn = 0;
dfs2(r, r, curdfn);
vector <int> b(n + 1);
for(int i = 1; i <= n; i++){
b[i] = a[rank[i]];
}
tr.init(b);
}
int lca(int x, int y){
while(head[x] != head[y]){
if(dep[head[x]] < dep[head[y]]) y = father[head[y]];
else x = father[head[x]];
}
return (dep[x] < dep[y] ? x : y);
}
void modify_path(int x, int y, int val){
while(head[x] != head[y]){
if(dep[head[x]] < dep[head[y]]){
tr.modify(dfn[head[y]], dfn[y], val);
y = father[head[y]];
}
else{
tr.modify(dfn[head[x]], dfn[x], val);
x = father[head[x]];
}
}
if(dfn[x] > dfn[y]) swap(x, y);
tr.modify(dfn[x], dfn[y], val);
}
int query_path(int x, int y){
int ans = 0;
while(head[x] != head[y]){
if(dep[head[x]] < dep[head[y]]){
ans += tr.query(dfn[head[y]], dfn[y]);
y = father[head[y]];
}
else{
ans += tr.query(dfn[head[x]], dfn[x]);
x = father[head[x]];
}
ans %= p;
}
if(dfn[x] > dfn[y]) swap(x, y);
ans += tr.query(dfn[x], dfn[y]);
ans %= p;
return ans;
}
void modify_son(int idx, int val){
tr.modify(dfn[idx], dfn[idx] + siz[idx] - 1, val);
}
int query_son(int idx){
return tr.query(dfn[idx], dfn[idx] + siz[idx] - 1) % p;
}
void test(){
cout << "father:\n";
for(int i = 1; i <= n; i++) cout << father[i] << ' ';
cout << "\nsiz:\n";
for(int i = 1; i <= n; i++) cout << siz[i] << ' ';
cout << "\ndep:\n";
for(int i = 1; i <= n; i++) cout << dep[i] << ' ';
cout << "\nson:\n";
for(int i = 1; i <= n; i++) cout << son[i] << ' ';
cout << "\nhead:\n";
for(int i = 1; i <= n; i++) cout << head[i] << ' ';
cout << "\ndfn:\n";
for(int i = 1; i <= n; i++) cout << dfn[i] << ' ';
cout << "\nrank:\n";
for(int i = 1; i <= n; i++) cout << rank[i] << ' ';
}
void test_sgt(){
cout << "rank:\n";
for(int i = 1; i <= n; i++) cout << rank[i] << ' ';
cout << "\nval:\n";
for(int i = 1; i <= n; i++) cout << tr.query(i, i) << ' ';
cout << '\n';
}
}t;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> r >> p;
vector <vector <int>> v(n + 1);
vector <int> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i < n; i++){
int x, y;
cin >> x >> y;
v[x].push_back(y), v[y].push_back(x);
}
t.init(n, a, v);
// t.test();
// t.test_sgt();
while(m--){
int tmp;
cin >> tmp;
if(tmp == 1){
int x, y, val;
cin >> x >> y >> val;
t.modify_path(x, y, val % p);
}else if(tmp == 2){
int x, y;
cin >> x >> y;
cout << t.query_path(x, y) % p << '\n';
}else if(tmp == 3){
int idx, val;
cin >> idx >> val;
t.modify_son(idx, val % p);
}else{
int idx;
cin >> idx;
cout << t.query_son(idx) % p << '\n';
}
// t.test_sgt();
}
return 0;
}
全部评论 4
重剖吗
1周前 来自 北京
01
1周前 来自 湖南
0
%%%%%%%%%%%%%%%
1周前 来自 北京
0%%%
1周前 来自 江苏
0nmnmn
1周前 来自 湖南
0你又不是不会
1周前 来自 湖南
0
d
1周前 来自 湖南
0
有帮助,赞一个