题意：一棵树，多次给指定链上的节点加1，问最大节点权值

n个点，n-1条边很容易惯性想成一条链，幸好有样例..

 

简单的树剖即可！（划去）

正常思路是树上差分，毕竟它就询问一次..

#include
      
       #include
       
        #include
        
         using namespace std;inline int rd(){    int ret=0,f=1;char c;    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;    while(isdigit(c))ret=ret*10+c-'0',c=getchar();    return ret*f;}const int MAXN=500005<<2;struct Edge{    int next,to;    Edge(int x=0,int     y=0){next=x;to=y;}}e[MAXN];int ecnt,head[MAXN];inline void add(int x,int y){    e[++ecnt]=Edge(head[x],y);    head[x]=ecnt;}int n,m;int fa[MAXN],dep[MAXN],siz[MAXN],hs[MAXN];void dfs1(int x,int pre){    fa[x]=pre;dep[x]=dep[pre]+1;siz[x]=1;    int mx=0,tmp=0;    for(int i=head[x];i;i=e[i].next){        int v=e[i].to;        if(v==pre) continue;        dfs1(v,x);        siz[x]+=siz[v];        if(siz[v]>mx){mx=siz[v];tmp=v;}    }    hs[x]=tmp;}int top[MAXN],id[MAXN],tot;void dfs2(int x,int tp){    top[x]=tp;id[x]=++tot;    if(hs[x]) dfs2(hs[x],tp);    for(int i=head[x];i;i=e[i].next){        int v=e[i].to;        if(v==fa[x]||v==hs[x]) continue;        dfs2(v,v);    }}int lca(int x,int y){    int ret;    while(top[x]!=top[y]){        dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];    }    return dep[x]
        
       
      

#include
      
       #include
       
        #include
        
         using namespace std;inline int rd(){    int ret=0,f=1;char c;    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;    while(isdigit(c))ret=ret*10+c-'0',c=getchar();    return ret*f;}const int MAXN=500005<<2;struct Edge{    int next,to;    Edge(int x=0,int     y=0){next=x;to=y;}}e[MAXN];int ecnt,head[MAXN];inline void add(int x,int y){    e[++ecnt]=Edge(head[x],y);    head[x]=ecnt;}int n,m;struct Seg{    #define ls (cur<<1)    #define rs (cur<<1|1)    #define mid (l+r>>1)    int mx[MAXN],add[MAXN];    Seg(){memset(mx,0,sizeof(mx));memset(add,0,sizeof(add));}    void pushup(int cur){        mx[cur]=max(mx[ls],mx[rs]);    }    void pushdown(int cur,int l,int r){        int v=add[cur];        add[ls]+=v;add[rs]+=v;        mx[ls]+=v;mx[rs]+=v;        add[cur]=0;    }    void build(int cur,int l,int r){        if(l==r) {mx[cur]=0;return;}        build(ls,l,mid);build(rs,mid+1,r);        pushup(cur);    }    void update(int L,int R,int cur,int l,int r,int w){        if(L<=l&&r<=R){mx[cur]+=w;add[cur]+=w;return;}        pushdown(cur,l,r);        if(L<=mid) update(L,R,ls,l,mid,w);        if(mid 
         
          mx){mx=siz[v];tmp=v;}    }    hs[x]=tmp;}int top[MAXN],id[MAXN],tot;void dfs2(int x,int tp){    top[x]=tp;id[x]=++tot;    if(hs[x]) dfs2(hs[x],tp);    for(int i=head[x];i;i=e[i].next){        int v=e[i].to;        if(v==fa[x]||v==hs[x]) continue;        dfs2(v,v);    }}void updateLink(int x,int y,int w){    while(top[x]!=top[y]){        if(dep[top[x]]
          
           dep[y]) swap(x,y);    T.update(id[x],id[y],1,1,n,w);}        int main(){    n=rd();m=rd();    int x,y;    for(int i=1;i<=n-1;i++){        x=rd();y=rd();        add(x,y);add(y,x);    }    dfs1(1,0);    dfs2(1,1);    T.build(1,1,n);     for(int i=1;i<=m;i++){        x=rd();y=rd();        updateLink(x,y,1);    }    cout<