[题解] P4556 [Vani有约会]雨天的尾巴
·题目大意
给定一棵树,有m次修改操作,每次修改 \(( x\) \(y\) \(z )\) 表示 \((x,y)\) 之间的路径上数值 \(z\) 的个数 \(+1\) 。最后求每个节点上数量最多的数是哪个,如果有多个相同的则输出较小的。
·思路分析
想到用线段树合并+树上差分。由于值存储在点上,所以在 \(fa[LCA(x,y)],LCA(x,y)\) 上 \(-1\),在\(x,y\) 上 \(+1\) 即可。
注意线段树在 \(pushup()\) 时要记得更新是哪个数字数量最多。
·代码实现
#include <bits/stdc++.h>
#define reg register
using namespace std;
namespace io{
char ch[20];
template<typename T>inline void read(T &x){
x=0;
char ch,f=0;
while(!isdigit(ch=getchar()))f|=ch=='-';
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;
}
template<typename T>inline void write(T x){
(x<0)&&(x=-x,putchar('-'));
(x)||(putchar('0'));
reg int i=0;
while(x)ch[i++]=x%10^48,x/=10;
while(i)putchar(ch[--i]);
}
} //快读快写
#define rd io::read
#define wt io::write
using namespace std;
const int maxN=200100;
int son[maxN],dep[maxN],fa[maxN],top[maxN],rt[maxN],head[maxN];
int tot,d[maxN],n,m,ans[maxN],cnt;
stack<int>st;
struct Seg_Tree{
int ch[2],val,id;
}t[maxN<<5];
struct Edge{
int to,next;
}e[maxN<<1];
inline void add(int x,int y){e[++tot]={y,head[x]};head[x]=tot;}
void dfs1(int),dfs2(int,int),solve(int),pup(int),del(int);
int LCA(int,int),merge(int,int,int,int);
void update(int,int,int&,int,int);
int main(){
rd(n);rd(m);
for(reg int i=1;i<n;++i){
int x,y;
rd(x);rd(y);
add(x,y);add(y,x);
}
dfs1(1);memset(top,0,sizeof(top));
dfs2(1,1);
for(reg int i=1;i<=m;++i){
int x,y,z,k;
rd(x);rd(y);rd(z);
k=LCA(x,y);
update(1,100000,rt[fa[k]],z,-1);update(1,100000,rt[k],z,-1);
update(1,100000,rt[x],z,1);update(1,100000,rt[y],z,1);
}
solve(1);
for(reg int i=1;i<=n;++i){
wt(ans[i]);putchar('\n');
}
return 0;
}
void solve(int x){
for(reg int i=head[x];i;i=e[i].next){
int s=e[i].to;
if(s==fa[x])continue;
solve(s);
rt[x]=merge(1,100000,rt[x],rt[s]);
}
ans[x]=t[rt[x]].id;
if(t[rt[x]].val==0)ans[x]=0;
}
int merge(int l,int r,int x,int y){
if(!x||!y)return x+y;
if(l==r){
t[x].val+=t[y].val;
t[x].id=l;
return x;
}
int mid=l+r>>1;
t[x].ch[0]=merge(l,mid,t[x].ch[0],t[y].ch[0]);
t[x].ch[1]=merge(mid+1,r,t[x].ch[1],t[y].ch[1]);
pup(x);del(y);
return x;
}
void del(int x){t[x]={0,0,0};st.push(x);}
void pup(int x){
if(t[t[x].ch[0]].val>=t[t[x].ch[1]].val)t[x].val=t[t[x].ch[0]].val,t[x].id=t[t[x].ch[0]].id;
else t[x].val=t[t[x].ch[1]].val,t[x].id=t[t[x].ch[1]].id;
}
void update(int l,int r,int &k,int x,int v){
if(!k){
if(st.empty())k=++cnt;
else k=st.top(),st.pop();
}
if(l==r){
t[k].val+=v;t[k].id=l;
return;
}
int mid=l+r>>1;
if(x<=mid)update(l,mid,t[k].ch[0],x,v);
else update(mid+1,r,t[k].ch[1],x,v);
pup(k);
}
void dfs1(int x){
dep[x]=dep[fa[x]]+1;top[x]=1;
int mxson=-1;
for(reg int i=head[x];i;i=e[i].next){
int s=e[i].to;
if(dep[s])continue;
fa[s]=x;dfs1(s);top[x]+=top[s];
if(top[s]>mxson)mxson=top[s],son[x]=s;
}
}
void dfs2(int x,int u){
top[x]=u;
if(son[x])dfs2(son[x],u);
for(reg int i=head[x];i;i=e[i].next){
int s=e[i].to;
if(top[s])continue;
dfs2(s,s);
}
}
int LCA(int x,int y){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}//树链剖分求LCA