P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并
P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并
涉及
- 树上差分
- 树剖求LCA
- 线段树动态开点
- 线段树合并
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL int
#define id(p) tree[p].id
#define ls(p) tree[p].ls
#define rs(p) tree[p].rs
#define ma(p) tree[p].ma
const int N=200005,M=300005;
LL n,m,k,u,v,w,x,y,z,ans[N];
LL head[M],net[M],val[M],idx;
LL d[N],siz[N],f[N],son[N],tp[N],id[N],rks[N],cnt;
LL root[N],tot;
struct node{
LL id,ls,rs,ma;
}tree[N*40];
LL read(){
LL s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return w*s;
}
void add(LL x,LL y){
val[++idx]=y;
net[idx]=head[x];
head[x]=idx;
return ;
}
void dfs1(LL x,LL fa){
f[x]=fa,d[x]=d[fa]+1,siz[x]=1;
for(int i=head[x];i;i=net[i]){
LL v=val[i];
if(v==fa) continue;
dfs1(v,x);
siz[x]+=siz[v];
if(siz[son[x]]<siz[v]) son[x]=v;
}
return ;
}
void dfs2(LL x,LL top){
tp[x]=top,id[x]=++cnt;
rks[cnt]=x;
if(son[x]){dfs2(son[x],top);}
for(int i=head[x];i;i=net[i]){
LL v=val[i];
if(v==son[x]||v==f[x]) continue;
dfs2(v,v);
}
return ;
}
LL lca(LL x,LL y){
while(tp[x]!=tp[y]){
if(d[tp[x]]<d[tp[y]]) swap(x,y);
x=f[tp[x]];
}
if(id[x]>id[y]) swap(x,y);
return x;
}
LL build(){
tot++;
ls(tot)=rs(tot)=ma(tot)=0;
id(tot)=1e9;
return tot;
}
void insert(LL x,LL p,LL l,LL r,LL val,LL z){
if(l==r){
ma(p)+=z;
id(p)=val;
return ;
}
LL mid=(l+r)>>1;
if(val<=mid) {
if(!ls(p)) ls(p)=build();
insert(x,ls(p),l,mid,val,z);
}
else{
if(!rs(p)) rs(p)=build();
insert(x,rs(p),mid+1,r,val,z);
}
if(ma(ls(p))>ma(rs(p))){
ma(p)=ma(ls(p));
id(p)=id(ls(p));
}else{
if(ma(ls(p))==ma(rs(p))){
id(p)=min(id(ls(p)),id(rs(p)));
ma(p)=ma(ls(p));
}else{
ma(p)=ma(rs(p));
id(p)=id(rs(p));
}
}
return ;
}
LL merge(LL p,LL q,LL l,LL r){
if(!p) return q;
if(!q) return p;
if(l==r){
ma(p)+=ma(q);
id(p)=l;
return p;
}
LL mid=(l+r)>>1;
ls(p)=merge(ls(p),ls(q),l,mid);
rs(p)=merge(rs(p),rs(q),mid+1,r);
if(ma(ls(p))>ma(rs(p))){
ma(p)=ma(ls(p));
id(p)=id(ls(p));
}else{
if(ma(ls(p))==ma(rs(p))){
id(p)=min(id(ls(p)),id(rs(p)));
ma(p)=ma(ls(p));
}else{
ma(p)=ma(rs(p));
id(p)=id(rs(p));
}
}
return p;
}
void dfs(LL p){
if(siz[p]==1){
ans[p]=id(root[p]);
return ;
}
for(int i=head[p];i;i=net[i]){
LL v=val[i];
if(v==f[p]) continue;
dfs(v);
root[p]=merge(root[p],root[v],1,1e5);
}
ans[p]=id(root[p]);
return ;
}
int main(){
n=read(),m=read();
for(int i=1;i<n;i++){
x=read(),y=read();
add(x,y);add(y,x);
root[i]=build();
}
root[n]=build();
dfs1(1,1);
dfs2(1,1);
for(int i=1;i<=m;i++){
x=read(),y=read(),z=read();
LL la=lca(x,y);
insert(x,root[x],1,1e5,z,1);
insert(y,root[y],1,1e5,z,1);
insert(la,root[la],1,1e5,z,-1);
if(la!=f[la])
insert(f[la],root[f[la]],1,1e5,z,-1);
}
dfs(1);
for(int i=1;i<=n;i++){
printf("%d\n",ans[i]!=1e9?ans[i]:0);
}
return 0;
}