【线段树合并/树上差分】P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并
思路
对 \(x,y,lca(u,v),fa_{lca(u,v)}\) 四个点进行树上差分,然后用线段树合并动态权值线段树。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
template<class Node>
struct PersidentSegmentTree {
#define lc(u) tr[u].l
#define rc(u) tr[u].r
const int n;
int tot = 0;
vector<Node> tr;
vector<int> root;
PersidentSegmentTree(): n(0) {}
PersidentSegmentTree(int n_): n(n_) {
int N = (n << 6) + 10;
tr.reserve(N); root.reserve(N);
tr.resize(N); root.resize(N);
}
PersidentSegmentTree(vector<int>& a): PersidentSegmentTree(a.size() - 1) {
function<void(int&, int, int)> build = [&](int& now, int l, int r) {
now = ++ tot;
if (l == r) {
return ;
}
int m = (l + r) >> 1;
build(lc(now), l, m);
build(rc(now), m + 1, r);
};
build(root[0], 1, n);
}
//上传
void pushup(int u) {
if (tr[lc(u)].Sum >= tr[rc(u)].Sum) {
tr[u].Sum = tr[lc(u)].Sum;
tr[u].pos = tr[lc(u)].pos;
} else {
tr[u].Sum = tr[rc(u)].Sum;
tr[u].pos = tr[rc(u)].pos;
}
}
//动态开点/更新树结点
void insert(int& now, int l, int r, int pos, int w) {
if (!now)
now = ++ tot;
if (l == r) {
tr[now].Sum += w;
tr[now].pos = pos;
return;
}
int m = l + r >> 1;
if (pos <= m)
insert(lc(now), l, m, pos, w);
else
insert(rc(now), m + 1, r, pos, w);
pushup(now);
}
//开新前缀树,last代表前缀,now代表新树根
void insert(int& now, int last, int l, int r, int pos, int w) {
now = ++ tot;
tr[now] = tr[last];
if (l == r) {
return;
}
int m = l + r >> 1;
if (pos <= m)
insert(lc(now), lc(last), l, m, pos, w);
else
insert(rc(now), rc(last), m + 1, r, pos, w);
}
//单点
int query(int now, int l, int r, int pos) {
if (l == r) {
return tr[now].Sum;
}
int m = l + r >> 1;
if (pos <= m)
return query(lc(now), l, m, pos);
else
return query(rc(now), m + 1, r, pos);
}
//区间查询 [u,v]->[root[l-1],root[r]]
int query(int u, int v, int l, int r, int pos) {
if (l == r) {
return tr[u].Sum;
}
int m = l + r >> 1;
if (pos <= m)
return query(lc(u), lc(v), l, m, pos);
else
return query(rc(u), rc(v), m + 1, r, pos);
}
void merge(int &u, int v, int l, int r) {
if (!u || !v) {
u = u + v;
return;
}
if (l == r) {
tr[u].Sum += tr[v].Sum;
return ;
}
int m = l + r >> 1;
merge(lc(u), lc(v), l, m);
merge(rc(u), rc(v), m + 1, r);
pushup(u);
}
};
struct Node {
int l, r;
int Sum = 0, pos = 0;
};
constexpr int N = 1e5 + 10, M = N - 10, logn = 20;
PersidentSegmentTree<Node> pst(N);
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector g(n + 1, vector<int>());
for (int i = 1; i < n; i ++) {
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
vector dep(n + 1, 0);
vector f(n + 1, vector<int>(logn + 1));
auto dfs = [&](auto && self, int u, int fa)->void{
f[u][0] = fa;
dep[u] = dep[fa] + 1;
for (int i = 1; i <= logn; i ++) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (auto v : g[u]) {
if (v == fa)continue;
self(self, v, u);
}
};
dfs(dfs, 1, 0);
auto lca = [&](int u, int v)->int{
if (dep[u] < dep[v])
swap(u, v);
for (int i = logn; i >= 0 ; i --) {
if (dep[f[u][i]] >= dep[v]) {
u = f[u][i];
}
}
if (u == v)
return u;
for (int i = logn; i >= 0; i --) {
if (f[u][i] != f[v][i]) {
u = f[u][i], v = f[v][i];
}
}
return f[u][0];
};
while (m --) {
int x, y, z;
cin >> x >> y >> z;
int k = lca(x, y);
pst.insert(pst.root[x], 1, M, z, 1);
pst.insert(pst.root[y], 1, M, z, 1);
pst.insert(pst.root[k], 1, M, z, -1);
pst.insert(pst.root[f[k][0]], 1, M, z, -1);
}
vector<int> ans(n + 1);
auto calc = [&](auto && self, int u, int fa)->void{
for (auto v : g[u]) {
if (v == fa) continue;
self(self, v, u);
pst.merge(pst.root[u], pst.root[v], 1, M);
}
ans[u] = pst.tr[pst.root[u]].pos;
if (!pst.tr[pst.root[u]].Sum) ans[u] = 0;
};
calc(calc, 1, 0);
for (int i = 1; i <= n; i ++)
cout << ans[i] << "\n";
return 0;
}
标签:int,P4556,线段,合并,pos,tr,root,Sum,pst
From: https://www.cnblogs.com/Kescholar/p/18350411