给一颗树，每次操作将一段路径上的点的某一个属性的属性值加一，求所有操作完成后每个点属性值最大的属性
只有一次询问，这个条件很重要
对原树剖分完之后，考虑处理每一个区间，用差分的思想，将\(l\)对应的属性值加1，\(r+1\)对应的属性值建1，最后从1到n遍历所有点即可
但是怎么叠加属性值呢？前面的操作就是单点修改，要求的是最大值，显然值域线段树
Code
#include<bits/stdc++.h> #define N 100005 using namespace std; int n,m,ans[N]; int seg[N],rev[N],dep[N],son[N],fa[N],size[N],top[N],hfu; int maxpos[N<<2],maxval[N<<2];//权值线段树 struct Node { int x,y; Node(int xx=0,int yy=0) {x=xx;y=yy;} }; struct Edge { int next,to; }edge[N<<1];int head[N],cnt=1; vector<Node> modi[N]; void add_edge(int from,int to) { edge[++cnt].next=head[from]; edge[cnt].to=to; head[from]=cnt; } template <class T> void read(T &x) { char c;int sign=1; while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48; while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign; } void dfs1(int rt) { size[rt]=1; dep[rt]=dep[fa[rt]]+1; for(int i=head[rt];i;i=edge[i].next) { int v=edge[i].to; if(v==fa[rt]) continue; fa[v]=rt; dfs1(v); size[rt]+=size[v]; if(size[son[rt]]<size[v]) son[rt]=v; } } void dfs2(int rt) { if(son[rt]) { seg[son[rt]]=++hfu; rev[hfu]=son[rt]; top[son[rt]]=top[rt]; dfs2(son[rt]); } for(int i=head[rt];i;i=edge[i].next) { int v=edge[i].to; if(v==fa[rt]||v==son[rt]) continue; seg[v]=++hfu; rev[hfu]=v; top[v]=v; dfs2(v); } } void modif(int x,int y,int z) { modi[x].push_back(Node(z,1)); modi[y+1].push_back(Node(z,-1)); } void modify_edge(int x,int y,int z) { int fx=top[x],fy=top[y]; while(fx!=fy) { if(dep[fx]<dep[fy]) { swap(fx,fy); swap(x,y); } modif(seg[fx],seg[x],z); x=fa[fx];fx=top[x]; } if(dep[x]>dep[y]) swap(x,y); modif(seg[x],seg[y],z); } void pushup(int rt) { if(maxval[rt<<1] >= maxval[rt<<1|1]) maxpos[rt]=maxpos[rt<<1],maxval[rt]=maxval[rt<<1]; else maxpos[rt]=maxpos[rt<<1|1],maxval[rt]=maxval[rt<<1|1]; } void modify(int rt,int l,int r,int x,int val) { if(l==x&&r==x) { maxval[rt]+=val; return; } int mid=(l+r)>>1; if(x<=mid) modify(rt<<1,l,mid,x,val); else modify(rt<<1|1,mid+1,r,x,val); pushup(rt); } void build(int rt,int l,int r) { if(l==r) { maxval[rt]=0; maxpos[rt]=l; return; } int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); pushup(rt); } int main() { read(n);read(m); for(int i=1;i<n;++i) { int x,y; read(x);read(y); add_edge(x,y); add_edge(y,x); } seg[1]=rev[1]=top[1]=hfu=1; dfs1(1); dfs2(1); build(1,1,100000); while(m--) { int x,y,z; read(x);read(y);read(z); modify_edge(x,y,z); } for(int i=1;i<=n;++i) { for(vector<Node>::iterator it = modi[i].begin(); it != modi[i].end(); ++it) { int loc=it->x,v=it->y; modify(1,1,100000,loc,v); } ans[rev[i]]=(maxval[1] ? maxpos[1] : 0); } for(int i=1;i<=n;++i) printf("%d\n",ans[i]); return 0; }转载于:https://www.cnblogs.com/Chtholly/p/11573799.html
相关资源：JAVA上百实例源码以及开源项目