“我家门前有两棵树，一颗是线段树，另一颗也是线段树。
我把他们合并了起来，就成了一道紫题。”
————NTL
终于！！！
在DeepSeek的帮助下！
耗时1.919810小时！
一道线段树合并的模板新鲜出炉！
#include<iostream>
#include<vector>
using namespace std;
/*房屋的个数，救济粮发放的次数，最后的边的位置列表*/
int n,m,h[114514];
struct awa{
int to,nxt;
};vector<awa>g;/*交织链表存图()*/
void addEdge(const int &ef,const int &et){
g.push_back((awa){et,h[ef]});
h[ef]=g.size()-1;
return ;
}/*建边操作*/
/*深度列表，二进制父节点表，log_2(i)+1列表*/
int dep[114514],fa[114514][26],lg[114514]={0};
inline void dfsclca(int x,int fu){
/*初始化为比父节点深一层*/
dep[x]=dep[fu]+1;
/*初始化0级父节点*/
fa[x][0]=fu;
/*递推预处理父节点*/
for(int i=1;i<=lg[dep[x]];i++){
/*x级父节点就是x-1级父节点的x-1级父节点*/
fa[x][i]=fa[fa[x][i-1]][i-1];
/*2^x==2^(x-1)+2^(x-1)*/
}/*自己悟awa*/
/*遍历子节点*/
for(int i=h[x];i>=0;i=g[i].nxt){
if(g[i].to!=fu){dfsclca(g[i].to,x);}
}/*预处理子节点*/
return/*深搜预处理*/;
}
int lca(int a,int b){/*求LCA*/
if(dep[a]<dep[b]){
/*my_swap()*/
a+=b;b=a-b;a-=b;
}/*保证a比b深*/
while(dep[a]>dep[b]){
a=fa[a][lg[dep[a]-dep[b]]-1];
}/*让较深的节点往上跳，直到深度相同*/
if(a==b){/*若跳到了同一处*/
/*这证明两节点为祖孙关系*/
return a;/*返回该节点*/
}else{/*若不在同一处*/
for(int ii=lg[dep[a]]-1;ii>=0;ii--){
/*若跳完之后不在同一处*/
if(fa[a][ii]!=fa[b][ii]){
a=fa[a][ii];b=fa[b][ii];
}/*往上跳*/
}/*直到就差一步*/
return fa[a][0];
}/*此时，两节点的父节点就是他们的 LCA*/
}
struct Nope{/*动态开点线段树*/
/*左儿子编号，右儿子编号*/
int ls=0,rs=0;
/*最多的救济粮类型，最多的救济粮数量*/
int ty=0,mc=0;
}tre[5141145];
/*树根列表：rot[i]表示节点i的线段树根*/
int nct=0,rot[114514];
/*任务列表：记录每个节点的差分事件*/
vector<pair<int,int> >task[114514];
/*first代表救济粮类型，second代表差分变化量*/
inline void push_up(int x){
if(tre[tre[x].ls].mc>tre[tre[x].rs].mc){
tre[x].mc=tre[tre[x].ls].mc;
tre[x].ty=tre[tre[x].ls].ty;
}else if(tre[tre[x].ls].mc<tre[tre[x].rs].mc){
tre[x].mc=tre[tre[x].rs].mc;
tre[x].ty=tre[tre[x].rs].ty;
}else{/*比较左右子树的最大次数，取较大的*/
if(tre[tre[x].ls].ty<tre[tre[x].rs].ty){
tre[x].mc=tre[tre[x].ls].mc;
tre[x].ty=tre[tre[x].ls].ty;
}else{/*取编号较小的*/
tre[x].mc=tre[tre[x].rs].mc;
tre[x].ty=tre[tre[x].rs].ty;
}
}
}/*更新节点信息*/
inline int mrg(int t1,int t2,int lft,int rit){
/*若有空树，则返回非空的那颗*/
if(!t1 || !t2){return t1+t2;}
if(lft==rit){/*若是叶子节点*/
tre[t1].mc+=tre[t2].mc;
/*将最多的救济粮数量相加*/
return t1;
}/*合并叶子节点*/
int mid=(lft+rit)>>1;
/*递归合并左子树*/
tre[t1].ls=mrg(tre[t1].ls,tre[t2].ls,lft,mid);
/*递归合并右子树*/
tre[t1].rs=mrg(tre[t1].rs,tre[t2].rs,mid+1,rit);
/*更新合并后的节点*/
push_up(t1);
/*返回合并后的节点*/
return t1;
}/*合并线段树*/
inline void upd(int &rt,int lft,int rit,int fod,int num){
if(!rt){rt=++nct;}
if(lft==rit){/*若是叶子节点*/
/*将最多的救济粮类型初始化*/
tre[rt].ty=fod;
/*将最多的救济粮数量初始化*/
tre[rt].mc+=num;
return ;
}/*若不是叶子节点*/
int mid=(lft+rit)>>1;
if(fod<=mid){/*若属于左子树*/
/*插入左子树*/
upd(tre[rt].ls,lft,mid,fod,num);
}else{/*若属于右子树*/
/*插入右子树*/
upd(tre[rt].rs,mid+1,rit,fod,num);
}/*更新根节点*/
push_up(rt);
return ;
}
/*答案列表*/
int ans[114514];
inline void dfs(int x,int fu){
for(int i=h[x];i>=0;i=g[i].nxt){
/*防止超级加辈()*/
if(g[i].to==fu){continue;}
dfs(g[i].to,x);/*处理子树*/
/*将子树的线段树合并到父节点的线段树*/
rot[x]=mrg(rot[x],rot[g[i].to],1,100005);
}/*遍历所有子节点*/
for(int i=0;i<task[x].size();i++){
upd(rot[x],1,100005,task[x][i].first,task[x][i].second);
}/*更新该节点所在的线段树*/
if(tre[rot[x]].mc>0){/*若存在救济粮*/
ans[x]=tre[rot[x]].ty;
/*取最大值对应类型*/
}else{/*若没有救济粮（村民：你们是不是忘了谁？）*/
ans[x]=0;
}/*答案为没有救济粮（村民：我救济粮呢？）*/
return/*深搜遍历整棵树*/;
}/*合并子树线段树并处理差分事件*/
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
h[i]=-1;/*初始化为无出边*/
lg[i]=lg[i-1]+(1<<lg[i-1]==i);
}/*预处理log_2(i)+1*/
for(int i=1,a,b;i<n;i++){
scanf("%d %d",&a,&b);
addEdge(a,b);addEdge(b,a);
}/*build_veillage_tree()*/
dfsclca(1,0);/*深搜预处理LCA (line 16)*/
for(int i=0,a,b,c,p;i<m;i++){
scanf("%d %d %d",&a,&b,&c);
/*求LCA (line 33)*/
p=lca(a,b);
/*树上差分（自己悟awa）X2*/
task[a].push_back({c,1});
task[b].push_back({c,1});
task[p].push_back({c,-1});
if(fa[p][0]){/*若LCA存在父节点*/
task[fa[p][0]].push_back({c,-1});
}
}
dfs(1,0);/*开始从根节点计算答案 (line 114(首))*/
for(int i=1;i<=n;i++){
printf("%d\n",ans[i]);
}/*输出*/
return/*结束了...可累死我力...*/0;
}/*P4556*/
打了本蒟蒻猫猫两个多小时……
码字不易，点个赞吧，球球了QwQ
顺带一提……
牛
# >w<