题意

给一颗树，每次操作将一段路径上的点的某一个属性的属性值加一，求所有操作完成后每个点属性值最大的属性

思路

树链剖分+权值线段树(\(O(nlog^2n)\))

只有一次询问，这个条件很重要

对原树剖分完之后，考虑处理每一个区间，用差分的思想，将\(l\)对应的属性值加1，\(r+1\)对应的属性值建1，最后从1到n遍历所有点即可

但是怎么叠加属性值呢？前面的操作就是单点修改，要求的是最大值，显然值域线段树

Code

#include
    
     #define N 100005using 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
     
       modi[N];void add_edge(int from,int to){    edge[++cnt].next=head[from];    edge[cnt].to=to;    head[from]=cnt;}template 
      
       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]]
       
        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
        
         ::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;}