题意
一棵 \(n\) 个节点的树，\(m\) 次修改，给 \(u\) 到 \(v\) 路径上每一个点一件种类为 \(z\) 的物品，求最后每个节点个数最多的物品种类。
思路
将题意再精简一下就是维护树上单点染色众数，修改是一条链。
（1）树上差分
想到修改一条路径其实可以用树上差分的思想，将路径划分为两部分 \(u\rightarrow \text{LCA}(u,v)\) 以及 \(\text{LCA}(u,v)\rightarrow v\)，我们的差分操作是对 \(u\) 和 \(v\) 种类 \(z\) 的统计 \(+1\)，对 \(\text{LCA}(u,v)\) 以及 \(fa(\text{LCA}(u,v))\) 种类 \(z\) 的统计 \(-1\)。
（2）求 \(\text{LCA}\)
轻重链剖分然后跳 \(top(u)\) 即可。
（3）线段树维护
因为每次只有“染色”操作，染色众数不需要回滚到原来的状态，于是我们可以用权值线段树来维护，对于每一个单点都建一棵权值线段树（要先离散化）。
（4）线段树合并
可以发现，节点 \(u\) 的信息修改一定是源自其内部节点的一条链，于是我们可以向上合并线段树，就等价于求差分数组的前缀和，即最终答案了。
代码
点击查看代码
int n,m;
struct Question{
int x,y,z;
}q[maxn];
struct Graph{
struct edge{
int to,nxt;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
}
int fa[maxn],son[maxn],dep[maxn],siz[maxn],top[maxn];
inline void dfs1(int u,int f,int d){
dep[u]=d,fa[u]=f,siz[u]=1;
int maxson=-1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f) continue;
dfs1(v,u,d+1);
siz[u]+=siz[v];
if(siz[v]>maxson){
maxson=siz[v],son[u]=v;
}
}
}
inline void dfs2(int u,int t){
top[u]=t;
if(!son[u]) return;
dfs2(son[u],t);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
inline int get_lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
if(dep[x]<dep[y]) return x;
else return y;
}
}G;
int rt[maxn],tot;
struct SegmentTree{
#define mid ((l+r)>>1)
int ch[maxm][2],siz[maxm],typ[maxm];
inline void push_up(int x){
if(siz[ch[x][0]]>=siz[ch[x][1]]){
siz[x]=siz[ch[x][0]],typ[x]=typ[ch[x][0]];
}
else{
siz[x]=siz[ch[x][1]],typ[x]=typ[ch[x][1]];
}
}
inline void insert(int &x,int l,int r,int p,int k){
if(!x) x=++tot;
if(l==r){
siz[x]+=k,typ[x]=l;
return;
}
if(p<=mid) insert(ch[x][0],l,mid,p,k);
else insert(ch[x][1],mid+1,r,p,k);
push_up(x);
}
inline void merge(int &x,int &y,int l,int r){
if(!x||!y){
x+=y;
return;
}
if(l==r){
siz[x]+=siz[y],typ[x]=l;
return;
}
merge(ch[x][0],ch[y][0],l,mid),merge(ch[x][1],ch[y][1],mid+1,r);
push_up(x);
}
}tree;
int maxx,ans[maxn];
vector<int> g;
inline void dfs(int u,int fa){
for(int i=G.head[u];i;i=G.e[i].nxt){
int v=G.e[i].to;
if(v==fa) continue;
dfs(v,u);
tree.merge(rt[u],rt[v],1,g.size());
}
if(tree.siz[rt[u]]){
ans[u]=g[tree.typ[rt[u]]-1];
}
}
int main(){
n=read(),m=read();
for(int i=1;i<n;i++){
int u=read(),v=read();
G.add_edge(u,v),G.add_edge(v,u);
}
G.dfs1(1,0,1);G.dfs2(1,1);
for(int i=1;i<=m;i++){
q[i].x=read(),q[i].y=read(),q[i].z=read();
g.push_back(q[i].z);
}
sort(g.begin(),g.end());
g.erase(unique(g.begin(),g.end()),g.end());
for(int i=1;i<=m;i++){
int l=G.get_lca(q[i].x,q[i].y);
int tmp=lower_bound(g.begin(),g.end(),q[i].z)-g.begin()+1;
tree.insert(rt[q[i].x],1,g.size(),tmp,1);
tree.insert(rt[q[i].y],1,g.size(),tmp,1);
tree.insert(rt[l],1,g.size(),tmp,-1);
if(G.fa[l]){
tree.insert(rt[G.fa[l]],1,g.size(),tmp,-1);
}
}
dfs(1,0);
for(int i=1;i<=n;i++){
printf("%d\n",ans[i]);
}
return 0;
}