Sone1
2025-05-23 21:03:42
发布于：山东
10阅读
0回复
0点赞
SATT 实现
```cpp
// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <iostream>
#include <memory.h>
#include <cassert>
#include <vector>
#include <queue>
#include <bits/stl_algo.h>
#define int long long
using namespace std;
const int N = 500010;
const int inf = 1e18;
int n, m;
template<const int NN = N>
struct SATT
{
int root, idx;
vector<int> adj[NN];
queue<int> pool;
struct Tree
{
int sum[3], siz[3], mx[3], mi[3], son[3], val, fa, rev, tag10, tag11, tag20, tag21;
Tree()
{
val = fa = rev = 0;
memset(sum, 0, sizeof sum);
memset(siz, 0, sizeof siz);
memset(son, 0, sizeof son);
tag10 = inf, tag11 = 0;
tag20 = inf, tag21 = 0;
// tag10 = tag11 = tag20 = tag21 = 0;
fill(mx, mx + 3, -inf);
fill(mi, mi + 3, inf);
}
} tree[NN];
int newnode()
{
int nw;
if (pool.size())
{
nw = pool.front();
pool.pop();
}
else
nw = ++idx;
tree[nw] = Tree();
return nw;
}
void pushup(int rt)
{
tree[rt].siz[0] = tree[tree[rt].son[0]].siz[0] + tree[tree[rt].son[1]].siz[0];
if (rt <= n)
++tree[rt].siz[0];
tree[rt].siz[1] = tree[tree[rt].son[2]].siz[0] + tree[tree[rt].son[2]].siz[1] + tree[tree[rt].son[0]].siz[1] + tree[tree[rt].son[1]].siz[1];
tree[rt].sum[0] = tree[tree[rt].son[0]].sum[0] + tree[tree[rt].son[1]].sum[0];
if (rt <= n)
tree[rt].sum[0] += tree[rt].val;//, cout << "add " << rt << ' ' << tree[rt].val << ' ' << tree[rt].sum[0] << '\n';
tree[rt].sum[1] = tree[tree[rt].son[2]].sum[0] + tree[tree[rt].son[2]].sum[1] + tree[tree[rt].son[0]].sum[1] + tree[tree[rt].son[1]].sum[1];
tree[rt].mx[0] = max(tree[tree[rt].son[0]].mx[0], tree[tree[rt].son[1]].mx[0]);
if (rt <= n)
tree[rt].mx[0] = max(tree[rt].mx[0], tree[rt].val);
tree[rt].mx[1] = max({tree[tree[rt].son[2]].mx[0], tree[tree[rt].son[2]].mx[1], tree[tree[rt].son[0]].mx[1], tree[tree[rt].son[1]].mx[1]});
tree[rt].mi[0] = min(tree[tree[rt].son[0]].mi[0], tree[tree[rt].son[1]].mi[0]);
if (rt <= n)
tree[rt].mi[0] = min(tree[rt].mi[0], tree[rt].val);
tree[rt].mi[1] = min({tree[tree[rt].son[2]].mi[0], tree[tree[rt].son[2]].mi[1], tree[tree[rt].son[0]].mi[1], tree[tree[rt].son[1]].mi[1]});
tree[rt].tag10 = inf, tree[rt].tag11 = 0;
tree[rt].tag20 = inf, tree[rt].tag21 = 0;
}
inline int isroot(int rt)
{
return tree[tree[rt].fa].son[0] == rt || tree[tree[rt].fa].son[1] == rt;
}
void pushrev(int rt)
{
if (!rt)
return;
tree[rt].rev ^= 1;
swap(tree[rt].son[0], tree[rt].son[1]);
}
void pushadd0(int rt, int tag10, int tag11, int tag20, int tag21)
{
// 0: cover
// 1: oth
if (tag10 != inf)
{
if (tree[rt].siz[0])
tree[rt].mi[0] = tree[rt].mx[0] = tag10;
if (tree[rt].siz[1])
tree[rt].mi[1] = tree[rt].mx[1] = tag10;
tree[rt].sum[0] = tag10 * tree[rt].siz[0];
tree[rt].sum[1] = tag10 * tree[rt].siz[1];
if (rt <= n)
tree[rt].val = tag10;
tree[rt].tag10 = tag10;
tree[rt].tag11 = 0;
tree[rt].tag20 = inf;
tree[rt].tag21 = 0;
}
if (rt <= n && tag20 != inf)
{
tree[rt].tag21 = 0;
tree[rt].mi[0] = tag20;
// tree[rt].mi[1] = tag20;
tree[rt].mx[0] = tag20;
// tree[rt].mx[1] = tag20;
tree[rt].val = tag20;
tree[rt].sum[0] = tag20 * tree[rt].siz[0];
tree[rt].tag20 = tag20;
}
if (tag11)
{
tree[rt].tag11 += tag11;
if (tree[rt].siz[1])
{
tree[rt].sum[1] += tree[rt].siz[1] * tag11;
tree[rt].mi[1] += tag11;
tree[rt].mx[1] += tag11;
}
}
if (tag21)
{
tree[rt].tag21 += tag21;
tree[rt].val += tag21;
tree[rt].sum[0] += tree[rt].siz[0] * tag21;
tree[rt].mi[0] += tag21;
tree[rt].mx[0] += tag21;
}
}
void pushadd1(int rt, int tag0, int tag1)
{
if (tag0 != inf)
{
if (rt <= n)
{
tree[rt].mi[0] = tag0;
tree[rt].mx[0] = tag0;
tree[rt].val = tag0;
tree[rt].sum[0] = tree[rt].siz[0] * tag0;
}
if (tree[rt].siz[1])
{
tree[rt].mi[1] = tag0;
tree[rt].mx[1] = tag0;
tree[rt].val = tag0;
tree[rt].sum[1] = tree[rt].siz[1] * tag0;
}
tree[rt].tag10 = tag0;
tree[rt].tag11 = 0;
tree[rt].tag20 = inf;
tree[rt].tag21 = 0;
}
if (tag1)
{
tree[rt].tag11 += tag1;
if (rt <= n)
{
tree[rt].tag21 += tag1;
tree[rt].mi[0] += tag1;
tree[rt].mx[0] += tag1;
tree[rt].val += tag1;
tree[rt].sum[0] += tree[rt].siz[0] * tag1;
}
if (tree[rt].siz[1])
{
tree[rt].mi[1] += tag1;
tree[rt].mx[1] += tag1;
tree[rt].sum[1] += tree[rt].siz[1] * tag1;
}
}
}
void pushdown(int rt)
{
if (tree[rt].rev)
{
if (tree[rt].son[0])
pushrev(tree[rt].son[0]);
if (tree[rt].son[1])
pushrev(tree[rt].son[1]);
tree[rt].rev = 0;
}
if (tree[rt].son[0])
pushadd0(tree[rt].son[0], tree[rt].tag10, tree[rt].tag11, tree[rt].tag20, tree[rt].tag21);
if (tree[rt].son[1])
pushadd0(tree[rt].son[1], tree[rt].tag10, tree[rt].tag11, tree[rt].tag20, tree[rt].tag21);
tree[rt].tag20 = inf;
tree[rt].tag21 = 0;
if (tree[rt].son[2])
pushadd1(tree[rt].son[2], tree[rt].tag10, tree[rt].tag11);
tree[rt].tag10 = inf;
tree[rt].tag11 = 0;
}
void pushlnk(int rt)
{
vector<int> v = {rt};
while (isroot(rt))
{
rt = tree[rt].fa;
v.emplace_back(rt);
}
reverse(v.begin(), v.end());
for (int &i : v)
pushdown(i);
}
void pushroot(int rt)
{
vector<int> v;
while (rt)
{
v.emplace_back(rt);
rt = tree[rt].fa;
}
reverse(v.begin(), v.end());
for (int &i : v)
pushdown(i);
}
void rotate(int x)
{
int y = tree[x].fa, z = tree[y].fa;
int o = (x == tree[y].son[1]) ? 1 : 0, oo = tree[x].son[o ^ 1];
if (tree[z].son[0] == y)
tree[z].son[0] = x;
else if (tree[z].son[1] == y)
tree[z].son[1] = x;
else if (tree[z].son[2] == y)
tree[z].son[2] = x;
tree[x].son[o ^ 1] = y;
tree[y].son[o] = oo;
tree[oo].fa = y;
tree[y].fa = x;
tree[x].fa = z;
pushup(y);
pushup(x);
}
void splay(int rt)
{
pushlnk(rt);
while (isroot(rt))
{
int o = tree[rt].fa, oo = tree[o].fa;
if (isroot(o))
{
int id = o;
if (tree[oo].son[0] == o && tree[o].son[0] != rt)
id = rt;
else if (tree[oo].son[0] != o && tree[o].son[0] == rt)
id = rt;
rotate(id);
}
rotate(rt);
}
}
void ins(int x, int y)
{
// tree[x].siz[1] += tree[y].siz[2];
// tree[x].siz[2] += tree[y].siz[2];
// tree[x].sum[1] ^= tree[y].sum[2];
// tree[x].sum[2] ^= tree[y].sum[2];
int id = newnode();
tree[id].son[2] = y;
tree[y].fa = id;
// tree[id].siz[1] = tree[id].siz[2] = tree[y].siz[2];
// tree[id].sum[1] = tree[id].sum[2] = tree[y].sum[2];
if (tree[x].son[2])
{
tree[tree[x].son[2]].fa = id;
tree[id].son[0] = tree[x].son[2];
}
tree[x].son[2] = id;
tree[id].fa = x;
pushup(id);
pushup(x);
}
void del(int x, int y)
{
// tree[x].siz[1] -= tree[y].siz[1];
// tree[x].siz[2] -= tree[y].siz[1];
// tree[x].sum[1] ^= tree[y].sum[1];
// tree[x].sum[2] ^= tree[y].sum[1];
splay(y);
if (!tree[y].son[0] && !tree[y].son[1])
{
tree[x].son[2] = 0;
pushup(x);
pool.emplace(y);
return;
}
else if (!tree[y].son[0])
{
tree[tree[y].son[1]].fa = x;
tree[x].son[2] = tree[y].son[1];
pushup(x);
pool.emplace(y);
return;
}
else if (!tree[y].son[1])
{
tree[tree[y].son[0]].fa = x;
tree[x].son[2] = tree[y].son[0];
pushup(x);
pool.emplace(y);
return;
}
else
{
int z = tree[y].son[0];
tree[y].son[0] = tree[z].fa = 0;
while (tree[z].son[1])
z = tree[z].son[1];
splay(z);
tree[z].son[1] = tree[y].son[1];
tree[tree[y].son[1]].fa = z;
tree[z].fa = x;
tree[x].son[2] = z;
pushup(z);
pushup(x);
pool.emplace(y);
return;
}
}
void access(int rt)
{
pushroot(rt);
splay(rt);
if (tree[rt].son[1])
ins(rt, tree[rt].son[1]);
tree[rt].son[1] = 0;
pushup(rt);
while (1)
{
splay(rt);
int o = tree[rt].fa;
if (!o)
break;
splay(o);
int oo = tree[o].fa;
splay(oo);
del(oo, o);
if (tree[oo].son[1])
ins(oo, tree[oo].son[1]);
tree[oo].son[1] = rt;
tree[rt].fa = oo;
pushup(oo);
rt = oo;
}
}
void makeroot(int rt)
{
access(rt);
splay(rt);
pushrev(rt);
}
int find(int rt)
{
access(rt);
splay(rt);
while (tree[rt].son[0])
{
pushdown(rt);
rt = tree[rt].son[0];
}
splay(rt);
return rt;
}
int link(int x, int y)
{
makeroot(x);
if (x == find(y))
return 0;
splay(y);
ins(y, x);
pushup(y);
return 1;
}
int cut(int x, int y)
{
makeroot(x);
access(y);
splay(y);
if (tree[y].son[0] != x || tree[x].son[1])
return 0;
tree[x].fa = tree[y].son[0] = 0;
pushup(y);
return 1;
}
inline void split(int x, int y)
{
makeroot(x);
access(y);
splay(y);
}
void chgfa(int x, int y)
{
if (x == root)
return;
makeroot(root);
access(x);
splay(x);
int o = tree[x].son[0];
pushdown(o);
while (tree[o].son[1])
{
pushdown(o);
o = tree[o].son[1];
}
cut(o, x);
makeroot(x);
pushup(o);
if (find(y) != x)
link(y, x);
else
link(o, x);
}
void modifycovtree(int x, int y)
{
split(root, x);
tree[x].val = y;
if (tree[x].son[2])
pushadd1(tree[x].son[2], y, 0);
pushup(x);
}
inline void modifycovlink(int x, int y, int z)
{
split(x, y);
pushadd0(y, inf, 0, z, 0);
}
int querytreemin(int x)
{
split(root, x);
// if (tree[x].son[2])
// pushadd1(tree[x].son[2], y, 0);
return min({tree[x].val, tree[tree[x].son[2]].mi[0], tree[tree[x].son[2]].mi[1]});
}
int querytreemax(int x)
{
split(root, x);
// if (tree[x].son[2])
// pushadd1(tree[x].son[2], y, 0);
return max({tree[x].val, tree[tree[x].son[2]].mx[0], tree[tree[x].son[2]].mx[1]});
}
void modifyaddtree(int x, int y)
{
split(root, x);
tree[x].val += y;
if (tree[x].son[2])
pushadd1(tree[x].son[2], inf, y);
pushup(x);
}
inline void modifyaddlink(int x, int y, int z)
{
split(x, y);
pushadd0(y, inf, 0, inf, z);
}
inline int querylinkmin(int x, int y)
{
split(x, y);
return tree[y].mi[0];
}
inline int querylinkmax(int x, int y)
{
split(x, y);
return tree[y].mx[0];
}
inline int querylinksum(int x, int y)
{
split(x, y);
return tree[y].sum[0];
}
inline int querytreesum(int x)
{
split(root, x);
return tree[x].val + tree[tree[x].son[2]].sum[0] + tree[tree[x].son[2]].sum[1];
}
void dfsbuild(int u, int fa = 0)
{
// cerr << "!!! " << u << ' ' << fa << '\n';
// _sleep(233);
for (int &v : adj[u])
if (v != fa)
{
dfsbuild(v, u);
link(u, v);
}
pushup(u);
}
} ; SATT satt;
signed main()
{
cin.tie(0)->sync_with_stdio(false);
cin >> n >> m;
satt.idx = n;
for (int i = 1; i < n; ++i)
{
int a, b;
cin >> a >> b;
satt.adj[a].emplace_back(b);
satt.adj[b].emplace_back(a);
}
for (int i = 1; i <= n; ++i)
{
int x;
cin >> x;
satt.tree[i].siz[0] = 1;
satt.tree[i].siz[1] = 0;
satt.tree[i].sum[0] = x;
satt.tree[i].sum[1] = 0;
satt.tree[i].mx[0] = x;
satt.tree[i].mx[1] = -inf;
satt.tree[i].mi[0] = x;
satt.tree[i].mi[1] = inf;
satt.tree[i].tag10 = inf;
satt.tree[i].tag11 = 0;
satt.tree[i].tag20 = inf;
satt.tree[i].tag21 = 0;
satt.tree[i].val = x;
}
cin >> satt.root;
// cerr << "jb\n";
satt.dfsbuild(satt.root);
// cerr << "bj\n";
while (m--)
{
int o;
cin >> o;
if (!o)
{
int x, y;
cin >> x >> y;
satt.modifycovtree(x, y);
}
else if (o == 1)
{
int x;
cin >> x;
satt.root = x;
}
else if (o == 2)
{
int x, y, z;
cin >> x >> y >> z;
satt.modifycovlink(x, y, z);
}
else if (o == 3)
{
int x;
cin >> x;
cout << satt.querytreemin(x) << '\n';
}
else if (o == 4)
{
int x;
cin >> x;
cout << satt.querytreemax(x) << '\n';
}
else if (o == 5)
{
int x, y;
cin >> x >> y;
satt.modifyaddtree(x, y);
}
else if (o == 6)
{
int x, y, z;
cin >> x >> y >> z;
satt.modifyaddlink(x, y, z);
}
else if (o == 7)
{
int x, y;
cin >> x >> y;
cout << satt.querylinkmin(x, y) << '\n';
}
else if (o == 8)
{
int x, y;
cin >> x >> y;
cout << satt.querylinkmax(x, y) << '\n';
}
else if (o == 9)
{
int x, y;
cin >> x >> y;
satt.chgfa(x, y);
}
else if (o == 10)
{
int x, y;
cin >> x >> y;
cout << satt.querylinksum(x, y) << '\n';
}
else
{
int x;
cin >> x;
cout << satt.querytreesum(x) << '\n';
}
}
return 0;
}
/*
5 5
2 1
3 1
4 1
5 2
4
1
4
1
2
1
10 2 3
3 1
7 3 4
6 3 3 2
9 5 1
*/
/*
9
1
1
*/
/*
10 12
2 1
3 2
4 2
5 3
6 4
7 5
8 2
9 4
10 9
791
868
505
658
860
623
393
717
410
173
4
0 8 800
1 4
2 8 2 103
3 9
4 4
5 7 304
6 8 8 410
7 10 8
8 1 8
9 6 9
10 2 3
11 5
*/
/*
173
860
103
791
608
1557
*/
有帮助，赞一个