直入主题:
学习线段树合并.....
从名字就能看出,这个东西要合并线段树.....
线段树怎么能合并呢......
暴力合就行了啊......
一次从上往下的遍历,把所有的节点信息暴力合并,然后就没有然后了.....
有两种合并方法:
一、动态开点
就是主席树那样的模式(可持久化了),新开一个点记录新的节点信息,但是空间~巨~大~无~比~
然后可能需要删除节点(以前的,既然合并了,就不需要旧的了233....)
二、静态开点(口胡的)
像启发式合并那样,直接把a的信息全加到b上(虽然没有任何启发式),但是可能破坏a树的形态
于是放一发模板题(本蒻第一次封装结构体233)
(感觉就是主席树233)
首先,思路树上差分,但是具体怎么玩呢?
一个暴力的思路:
对于每一个给定的补给点,建一棵权值线段树,其他的点也有线段树但是是空树,然后在差分的时候直接把所有的点给合并起来,最后统计答案。
线段树维护的是最值。
注意的是:差分:a+1,b+1,lca-1,lca的父节点+1,这个父节点是为了消除向上的影响,只维护路径上的值。
注释在代码:
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; int n,m; struct edge { int to,next; }e[maxn]; int head[maxn],cnt; inline void addedge(int from,int to) { e[++cnt].next=head[from]; e[cnt].to=to; head[from]=cnt; } int dep[maxn]; int f[maxn][40]; int dfs(int u,int fa) { dep[u]=dep[fa]+1; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v==fa) continue; dfs(v,u); f[v][0]=u; } } int rt[maxn]; struct segtree//第一次封装结构体 { int lc[maxn*40],rc[maxn*40],ma[maxn*40],id[maxn*40],root=0; void pushup(int p)//更新最值 { if(ma[lc[p]]>=ma[rc[p]]) { ma[p]=ma[lc[p]];id[p]=id[lc[p]];//值得注意的是:这个id是记录答案的,所以要一起更新 } else { ma[p]=ma[rc[p]];id[p]=id[rc[p]]; } } int merge(int a,int b,int l,int r) { if(!a||!b)//如果一个是空的,那就返回有值的那个节点 return a+b; if(l==r) { ma[a]=ma[a]+ma[b],id[a]=l;//如果是叶节点就更新 return a; } int mid=l+r>>1; lc[a]=merge(lc[a],lc[b],l,mid);//向下合并 rc[a]=merge(rc[a],rc[b],mid+1,r);//向下合并 pushup(a);//记得更新 return a; } void insert(int &x,int l,int r,int p,int k) { if(x==0) x=++root;//十分类似主席树的插入 if(l==r) { id[x]=l; ma[x]+=k; return; } int mid=l+r>>1; if(p<=mid)insert(lc[x],l,mid,p,k); else insert(rc[x],mid+1,r,p,k); pushup(x); } }T; int lca(int a,int b)//平淡无奇的lca { if(dep[a]<dep[b]) swap(a,b); for(int i=20;i>=0;i--) { if(dep[b]<=dep[a]-(1<<i)) a=f[a][i]; } if(a==b) return a; for(int i=20;i>=0;i--) { if(f[a][i]!=f[b][i]) { a=f[a][i]; b=f[b][i]; } } return f[a][0]; } int ans[maxn]; void dfsans(int u,int fa) { for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v==fa) continue; dfsans(v,u); rt[u]=T.merge(rt[u],rt[v],1,100000);//合并 } ans[u]=T.id[rt[u]];//更新答案 if(T.ma[rt[u]]==0) ans[u]=0;//记得特判0的情况 } int main() { scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } dfs(1,0); for(int i=1;i<=30;i++) { for(int j=1;j<=n;j++) { f[j][i]=f[f[j][i-1]][i-1]; } } for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); int u=lca(x,y); T.insert(rt[u],1,100000,z,-1); T.insert(rt[x],1,100000,z,1); T.insert(rt[y],1,100000,z,1); T.insert(rt[f[u][0]],1,100000,z,-1); } dfsans(1,0); for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; }
(完)