题解——P4556 [Vani有约会]雨天的尾巴
传送门
题意
一棵 \(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]]>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 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