简单的树链剖分+线段树

#include
      
       using namespace std;#define pb push_back#define lson root<<1,l,midd#define rson root<<1|1,midd+1,rconst int M=5e5+5;vector
       
        g[M];int tree[M<<2],lazy[M<<2],top[M],son[M],fa[M],sz[M],dfn[M],to[M],deep[M],cnt,n;void dfs1(int u,int f){    sz[u]=1;    fa[u]=f;    deep[u]=deep[f]+1;    for(int i=0;i
        
         sz[son[u]])                son[u]=v;        }    }}void dfs2(int u,int t){    dfn[u]=++cnt;    to[cnt]=u;    top[u]=t;    if(!son[u])        return ;    dfs2(son[u],t);    for(int i=0;i
         
          >1;    if(L<=midd)        update(L,R,w,lson);    if(R>midd)        update(L,R,w,rson);}void Update(int u,int v,int w){    while(top[u]!=top[v]){        if(deep[top[u]]
          
           >1;    if(pos<=midd)        return query(pos,lson);    if(pos>midd)        return query(pos,rson);}int main(){    scanf("%d",&n);    for(int i=1;i