https://www.luogu.com.cn/problem/P4556
题意概述
有 \(n\) 座房屋，构成一棵树。救济粮分 \(m\) 次发放，每次给 \(x\) 到 \(y\) 路径上每个房屋发放一袋 \(z\) 类型的救济粮。问所有救济粮发放完之后，每座房屋数量最多的救济粮类型，如果没有，输出 \(0\) 。
\(1 \leq n, m \leq 10^5\)，\(1 \leq z \leq 10^5\)。
思路
给 \(x\) 到 \(y\) 路径上所有节点分发同样的救济粮，考虑树上差分。
救济粮信息可以用值域线段树维护，最后统计答案的时候合并线段树即可。
具体的，动态开点，给每个节点建一棵值域线段树，维护该节点所有类型的救济粮中数量最大值，查询这个最大值对应的类型只需要在线段树上二分即可。
发放救济粮的过程，记 \(x\) 和 \(y\) 的 \(LCA\) 为 \(t\) ，\(x\) 和 \(y\) 节点的 \(z\) 类型救济粮数量 \(+1\)，\(t\) 和 \(t\) 的父节点的 \(z\) 类型救济粮数量 \(-1\) 。
最后向上合并线段树，计算每个节点答案即可，代码中使用了倍增求 \(LCA\) 。
时间复杂度 \(\mathcal{O}((n+m) \log N)\)，\(N\) 是 \(z\) 的上界。
代码
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 1e5+5;
const int INF = 1e9;class node{
public:int left=-1,right=-1,mx=0;
};void solve(){int n,m;cin >> n >> m;vector<vector<int>> adj(n+1);for (int i=0;i<n-1;i++){int u,v;cin >> u >> v;adj[u].push_back(v);adj[v].push_back(u);}vector<int> depth(n+1),par(n+1,-1); function<void(int)> dfs = [&](int u){for (auto& v:adj[u]){if (v==par[u]) continue;depth[v] = depth[u]+1;par[v] = u;dfs(v);}};dfs(1);vector<vector<int>> dp(n+1,vector<int>(32,-1));for (int i=1;i<=n;i++){dp[i][0] = par[i];}for (int k=1;k<32;k++){for (int i=1;i<=n;i++){if (dp[i][k-1]==-1) continue;dp[i][k] = dp[dp[i][k-1]][k-1]; }}auto getlca = [&](int u,int v){if (depth[u]<depth[v]){swap(u,v);}int diff = depth[u]-depth[v];for (int k=31;k>=0;k--){if (diff>>k&1){u = dp[u][k];}}if (u==v) return u;for (int k=31;k>=0;k--){if (dp[u][k]!=-1 && dp[v][k]!=-1 && dp[u][k]!=dp[v][k]){u = dp[u][k];v = dp[v][k];}}return par[u];};vector<node> seg{{}};vector<int> root(n+1);for (int i=1;i<=n;i++){seg.push_back({});root[i] = seg.size()-1;} function<void(int,int,int,int,int)> update = [&](int rt,int l,int r,int pos,int val){if (l==r){seg[rt].mx += val;return;}int mid = l+r >> 1;if (pos<=mid){if (seg[rt].left==-1){seg.push_back({});seg[rt].left = seg.size()-1;}update(seg[rt].left,l,mid,pos,val);} else{if (seg[rt].right==-1){seg.push_back({});seg[rt].right = seg.size()-1;}update(seg[rt].right,mid+1,r,pos,val);}seg[rt].mx = max(seg[rt].left!=-1?seg[seg[rt].left].mx:-INF,seg[rt].right!=-1?seg[seg[rt].right].mx:-INF);};while (m--){int x,y,z;cin >> x >> y >> z;int t = getlca(x,y);update(root[x],1,N,z,1);update(root[y],1,N,z,1);update(root[t],1,N,z,-1);if (par[t]!=-1) update(root[par[t]],1,N,z,-1);}function<int(int,int,int,int)> merge = [&](int rt1,int rt2,int l,int r){if (rt1==-1 || rt2==-1){return rt1==-1?rt2:rt1;}if (l==r){seg[rt1].mx = seg[rt1].mx+seg[rt2].mx;return rt1;}int mid = l+r >> 1;seg[rt1].left = merge(seg[rt1].left,seg[rt2].left,l,mid);seg[rt1].right = merge(seg[rt1].right,seg[rt2].right,mid+1,r);seg[rt1].mx = max(seg[rt1].left!=-1?seg[seg[rt1].left].mx:-INF,seg[rt1].right!=-1?seg[seg[rt1].right].mx:-INF);if (seg[rt1].mx==-INF){seg[rt1].mx = 0;}return rt1;};function<int(int,int,int,int)> first_valid = [&](int rt,int l,int r,int mx){if (rt==-1 || seg[rt].mx<mx){return -1;}if (l==r){return l;}int mid = l+r >> 1;int res = first_valid(seg[rt].left,l,mid,mx);if (res!=-1){return res;}return first_valid(seg[rt].right,mid+1,r,mx);};vector<int> res(n+1);function<void(int)> dfs2 = [&](int u){for (auto& v:adj[u]){if (v==par[u]) continue;dfs2(v);merge(root[u],root[v],1,N);}res[u] = seg[root[u]].mx==0?0:first_valid(root[u],1,N,seg[root[u]].mx);};dfs2(1);for (int i=1;i<=n;i++){cout << res[i] << '\n';}
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;// cin >> t;while (t--) solve();return 0;
}