题目描述
首先村落里的一共有 \(n\) 座房屋，并形成一个树状结构。然后救济粮分 \(m\) 次发放，每次选择两个房屋 \((x,~y)\)，然后对于 \(x\) 到 \(y\)的路径上(含 \(x\) 和 \(y\))每座房子里发放一袋 \(z\) 类型的救济粮。
然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。
思路
对每个点开一颗权值线段树，维护每个颜色出现的次数和出现最多的颜色，路径修改时差分，对权值线段树上相应位置修改，最后向上合并线段树
每个点最多开 \(\log n\) 个点，每次四个修改，数组大小开 \(4n\log n\)
#include <vector>
#include <cstdio>
using namespace std;
const int maxn = 1e5 + 10;
const int N = 2e6 + 10;
int n,m,cnt,fa[maxn],rt[maxn],ans[maxn],dep[maxn],siz[maxn],son[maxn],top[maxn],col[N<<2],mxv[N<<2],lson[N<<2],rson[N<<2];
vector<int> edge[maxn];
inline void init(int now,int f){
dep[now] = dep[f]+1;
siz[now] = 1;
fa[now] = f;
for (size_t i = 0;i < edge[now].size();i++) {
int to = edge[now][i];
if (to ^ f) {
init(to,now);
siz[now] += siz[to];
if (siz[son[now]] < siz[to]) son[now] = to;
}
}
}
inline void dfs(int now,int sum) {
top[now] = sum;
if (son[now]) dfs(son[now],sum);
for (size_t i = 0;i < edge[now].size();i++) {
int to = edge[now][i];
if (to ^ son[now] && to ^ fa[now]) dfs(to,to);
}
}
inline int lca(int u,int v) {
for (;top[u] ^ top[v];u = fa[top[u]])
if (dep[top[u]] < dep[top[v]]) swap(u,v);
return dep[u] < dep[v] ? u : v;
}
inline void pushup(int root) {
mxv[root] = max(mxv[lson[root]],mxv[rson[root]]);
col[root] = mxv[lson[root]] >= mxv[rson[root]] ? col[lson[root]] : col[rson[root]];
}
bool flag = false;
inline void update(int l,int r,int& root,int x,int v) {
if (l > x || r < x) return;
if (!root) root = ++cnt;
if (l == r) {
mxv[root] += v;
col[root] = x;
return;
}
int mid = l+r>>1;
update(l,mid,lson[root],x,v);
update(mid+1,r,rson[root],x,v);
pushup(root);
}
inline void merge(int l,int r,int &x,int y) {
if (!x || !y) return x += y,void();
if (l == r) {
mxv[x] += mxv[y];
col[x] = l;
return;
}
int mid = l+r>>1;
merge(l,mid,lson[x],lson[y]);
merge(mid+1,r,rson[x],rson[y]);
pushup(x);
}
inline void solve(int now) {
for (size_t i = 0;i < edge[now].size();i++) {
int to = edge[now][i];
if (to ^ fa[now]) {
solve(to);
merge(1,1e5,rt[now],rt[to]);
}
}
if (mxv[rt[now]]) ans[now] = col[rt[now]];
}
int main() {
scanf("%d%d",&n,&m);
for (int i = 1,u,v;i < n;i++) {
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
init(1,0);
dfs(1,1);
for (int u,v,w;m--;) {
scanf("%d%d%d",&u,&v,&w);
update(1,1e5,rt[u],w,1);
update(1,1e5,rt[v],w,1);
int l = lca(u,v);
update(1,1e5,rt[l],w,-1);
update(1,1e5,rt[fa[l]],w,-1);
}
solve(1);
for (int i = 1;i <= n;i++) printf("%d\n",ans[i]);
return 0;
}