Problem
$n$个点的树上进行$m$次操作，每次操作$(x,y,z)$，表示$x,y$的路径上所有点获得一个数$z$。求$m$次操作后每个点获得的数最多为哪一个？
Data Range
$1\leq n,m,x,y,z\leq 10^5$
Solution-线段树合并
Idea
首先，明确线段树合并的是动态开点线段树，其次合并时是将两棵树值相加。
动态开点线段树和正常的线段树写法基本一样，不过就是要另外开一个数组$l[node],r[node]$存储左右节点的编号。
动态开点线段树在合并时，假设将线段树$tr_2$合并到线段树$tr_1$中，首先同时访问左节点，如果有一棵树左节点为空，即相当于这棵树下面所有值为0，相加后没有影响，则直接接上另一棵树的左节点即可；右节点同理。直到到达某一个叶子节点，将$tr_2$的值加到$tr_1$上即可，再返回时$push\ up$。
Complexity Analyze
考虑$n$棵一个节点的线段树合并成$1$棵线段树，每个节点在合并时都会在它们于完整线段树的$lca$处作为停止点返回。可n以观察到第$i$层的节点会被访问$\frac{n}{2^{i -1}}$次，第$i$层有$2^{i - 1}$个节点，所以每层会被访问$n$次，共$\log n$层，时间复杂度$O(n\log n)$。
Approach
回到本题，在$x,y$处的线段树的$z$位置加$1$，在$lca(x,y)$处及其父亲的$z$位置减$1$。对树进行一次遍历，并做一次线段树合并即可。
时间复杂度$O(n\log n)$，但常数较大。
code
/*************************************************************************
> Author: Knowledge_llz
> Blog: https://www.luogu.com.cn/problem/P4556
************************************************************************/
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int maxx = 1e5 + 10;
int n, m, son[maxx], jump[maxx], sz[maxx], f[maxx], dep[maxx], ans[maxx], cnt = 0;
vector<int> edge[maxx];
queue<int> in[maxx], out[maxx];
int tr[maxx * 60], p[maxx * 60], rt[maxx], l[maxx * 60], r[maxx * 60];
void push_up(int node){
if(tr[l[node]] >= tr[r[node]]){
tr[node] = tr[l[node]];
p[node] = p[l[node]];
}
else{
tr[node] = tr[r[node]];
p[node] = p[r[node]];
}
}
int update(int node, int L, int R, int pos, int val){
if(!node) node = ++cnt;
if(L == R){ tr[node] += val; p[node] = L; return node; }
int mid = (L + R) / 2;
if(pos <= mid) l[node] = update(l[node], L, mid, pos, val);
else r[node] = update(r[node], mid + 1, R, pos, val);
push_up(node);
return node;
}
int merge(int node1, int node2, int L, int R){
if(!node1) return node2;
if(!node2) return node1;
if(L == R){ tr[node1] += tr[node2]; p[node1] = L; return node1; }
int mid = (L + R) >> 1;
l[node1] = merge(l[node1], l[node2], L, mid);
r[node1] = merge(r[node1], r[node2], mid + 1, R);
push_up(node1);
return node1;
}
int dfs1(int id, int fa){
sz[id] = 1;
f[id] = fa;
dep[id] = dep[fa] + 1;
for(auto v : edge[id]){
if(v != fa){
sz[id] += dfs1(v, id);
if(sz[v] > sz[son[id]]) son[id] = v;
}
}
return sz[id];
}
void dfs2(int id, int top){
jump[id] = top;
if(son[id]) dfs2(son[id], top);
for(auto v: edge[id]){
if(v != f[id] && v != son[id]) dfs2(v, v);
}
}
int LCA(int u, int v){
while(jump[u] != jump[v]){
if(dep[jump[u]] > dep[jump[v]]) swap(u, v);
v = f[jump[v]];
}
if(dep[u] > dep[v]) swap(u, v);
return u;
}
void dfs(int id){
for(auto v : edge[id]){
if(v != f[id]){
dfs(v);
rt[id] = merge(rt[id], rt[v], 1, 100000);
}
}
if(tr[rt[id]]) ans[id] = p[rt[id]];
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
cin >> n >> m;
for(int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs1(1, 0);
dfs2(1, 1);
while(m--){
int u, v, z, lca;
cin >> u >> v >> z;
lca = LCA(u, v);
rt[u] = update(rt[u], 1, 100000, z, 1);
rt[v] = update(rt[v], 1, 100000, z, 1);
rt[lca] = update(rt[lca], 1, 100000, z, -1);
if(f[lca]) rt[f[lca]] = update(rt[f[lca]], 1, 100000, z, -1);
}
dfs(1);
for(int i = 1; i <= n; ++i) cout << ans[i] << endl;
return 0;
}Solution-树链剖分
Approach
在树剖时对树上节点重新编号，将树转换为序列。对于一次询问$(x,y)$，直接树剖成$[a_1,b_1]$,$[a_2,b_2]…[a_n,b_n]$共$O(\log n)$段序列，对这些序列$a_i$处打上$+z$标记，$b_i$处打上$-z$标记。最后再按顺序扫描序列，用线段树维护。
时间复杂度：$O(n\log^2 n)$。但常数较小，实际运行速度比线段树合并做法快。
Code
/*************************************************************************
> File Name: 1.cpp
> Author: Knowledge_llz
> Mail: 925538513@qq.com
> Blog: https://www.cnblogs.com/Knowledge-Pig/
************************************************************************/
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
#define ls (node << 1)
#define rs (node << 1 | 1)
using namespace std;
const int maxx = 1e5 + 10;
int n, m, son[maxx], jump[maxx], ID[maxx], arcID[maxx], sz[maxx], f[maxx], dep[maxx], cnt = 0;
vector<int> edge[maxx];
queue<int> in[maxx], out[maxx];
int tr[maxx << 2], p[maxx << 2], ans[maxx];
void push_up(int node){
if(tr[ls] >= tr[rs]){
tr[node] = tr[ls];
p[node] = p[ls];
}
else{
tr[node] = tr[rs];
p[node] = p[rs];
}
}
void update(int node, int l, int r, int pos, int val){
if(l == r){ tr[node] += val; p[node] = l; return; }
int mid = (l + r) / 2;
if(pos <= mid) update(ls, l, mid, pos, val);
else update(rs, mid + 1, r, pos, val);
push_up(node);
}
int dfs1(int id, int fa){
sz[id] = 1;
f[id] = fa;
dep[id] = dep[fa] + 1;
for(auto v : edge[id]){
if(v != fa){
sz[id] += dfs1(v, id);
if(sz[v] > sz[son[id]]) son[id] = v;
}
}
return sz[id];
}
void dfs2(int id, int top){
ID[id] = ++cnt;
arcID[cnt] = id;
jump[id] = top;
if(son[id]) dfs2(son[id], top);
for(auto v: edge[id]){
if(v != f[id] && v != son[id]) dfs2(v, v);
}
}
void solve(int u, int v, int z){
while(jump[u] != jump[v]){
if(dep[jump[u]] > dep[jump[v]]) swap(u, v);
in[ID[jump[v]]].push(z);
out[ID[v]].push(z);
// cout << ID[jump[v]] << " " << ID[v] << endl;
v = f[jump[v]];
}
if(dep[u] > dep[v]) swap(u, v);
in[ID[u]].push(z);
out[ID[v]].push(z);
// cout << ID[u] << " " << ID[v] << endl;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for(int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs1(1, 0);
dfs2(1, 1);
while(m--){
int u, v, z;
cin >> u >> v >> z;
solve(u, v, z);
}
for(int i = 1; i <= n; ++i){
while(!in[i].empty()){
update(1, 1, 100000, in[i].front(), 1);
in[i].pop();
}
if(tr[1] > 0) ans[arcID[i]] = p[1];
else ans[arcID[i]] = 0;
while(!out[i].empty()){
update(1, 1, 100000, out[i].front(), -1);
out[i].pop();
}
}
for(int i = 1; i <= n; ++i) cout << ans[i] << endl;
return 0;
}
