区间信息维护

前缀和与差分

多维前缀和

多维前缀和可以通过一维一维处理的方式，将复杂度控制在可控范围。
例如二维前缀和求法：

1. $sum_{i,j}=a_{i,j}$
2. $sum_{i,j}+=sum_{i-1,j}$
3. $sum_{i,j}+=sum_{i,j-1}$

例题：NC225630 智乃酱的子集与超集。

数列上加多项式

给一个数列的一部分连续的数分别加上 $f(1),f(2),\dots,f(n),\dots$
key：任何一个最高次数为 $n$ 的多项式连续数列可以通过差分 $n+1$ 次表示。
因此，对于区间 $(l,r)$，我们先差分出一个从 $l$ 开始的 $f(1)$ 开始的数列，再差分出一个从 $r+1$ 开始的 $-f(r-l+2)$ 开始的数列抵消影响。
例题：NC225628 智乃酱的静态数组维护问题多项式。

树状数组与线段树

离线后树状数组

一些统计种类的问题可以通过这个方法来解决。
例如 [HEOI2012]采花

LazyTag

懒标记是线段树的核心之一。考虑需要维护的数值在懒标记下的运算很关键。
给出例题：
线段树
智乃酱的cube

带修改的 DP(DDP)

通过线段树可以完成一些能通过矩阵优化的 DP 的待修改版本。
智乃酱的双塔问题·极（带修改的DP，DDP）
智乃酱的双塔问题·改

势能线段树（带暴力成分的线段树）

有些数据具有单调性，就像势能不断下降至 0 势能点，观察并维护之可以让一些线段树结构看似有暴力修改，实则复杂度合法。
势能线段树模板题二
弩蚊怒夏

李超线段树

李超线段树是用来维护平面上的若干点的，用于快速找出在某一个 x 坐标，那一条的 y 值最大或最小。这在动态规划优化中也有作用。
模板：智乃的直线

平衡树

绝大部分时候，set 都可以解决问题，因此在比赛中非必要，不要贸然使用平衡树，平衡树在 ACM/ICPC 中并不是一个需要经常手写的数据结构。由于相较于 Treap，Splay 拥有更广泛的使用场合，因此此处只呈现 Splay 的代码。

平衡树管理数组的一个优势是他的区间长度是自由的，因此对于区间反转这一问题，线段树无法通过打 tag 来解决，而平衡树可以做到，这一类需要严格对某一个自由长度区间打 tag 的操作是平衡树之于线段树的优势。

我的博客中有对平衡树的详细学习笔记。

例题：

[HNOI2004]宠物收养所 请注意，本题可以通过 Set 解决，相较于手写平衡树，这是更优秀的选择。

普通平衡树 这是一道模板题

文艺平衡树 这是另一道模板题

跳表

首先，跳表是一种离线算法， 这是很重要的一点。

跳表（ST 表）有两种，一种是传统的 log 型跳表，建立复杂度为 $O(n\log n)$，但必须要满足所求的内容在区间重叠不影响结果（例如，gcd 或者 max/min）。

另一种是根号型跳表，记 $f_{i,j}$ 为从 $i$ 开始的 $j$ 个数的值（例如，和），记 $g_{i,j}$ 为从 $i$ 开始的 $block \times j$ 个数的和，通常我们令 $block=\operatorname{sqrt}(n)$。这样，我们可以在 $O(n \sqrt n)$ 的时间复杂度内建立跳表，然后在 $O(1)$ 的时间复杂度内进行单次查询（大块+小块）。请注意，只有当查询次数不小于数组总长的 $100$ 倍时才需要使用根号跳表，否则，线段树是一个更好的选择。不同于 log 型跳表，区间跳表只要满足区间可加性就能做（这与线段树的要求相同，不是吗）。

分块

对于一些问题，我们可以将整个区间分成 $\operatorname{sqrt}(n)$ 个块。如果我们可以记录每个块的总值，或是对无效的块打上标记，我们就可以保证每次查询的时间复杂度为 $O(\sqrt n)$。

莫队

普通莫队

普通莫队是一个离线算法。

我们先将整个区间分成 $\sqrt n$ 个块。对于所有查询 $[l,r]$，我们先根据 $l$ 所在的块进行升序排序，相同时再根据 $r$ 的大小进行升序排序。我们以这个顺序处理所有查询，对于一次查询，我们只需要访问上一次查询没有查询过的点，再删除该次查询没有但上一次查询有的点即可。时间复杂度为 $O(n\sqrt n)$。

例题：小Z的袜子

带修莫队

在普通莫队的前提下，如果题目有了单点修改的操作，我们就可以使用带修莫队。

待修莫队给了所有查询第三维时间戳，即代表这个查询经过了几次单点修改。对于所有查询 $[l,r,tim]$，我们先根据 $l$ 所在的块进行升序排序，相同时再根据 $r$ 所在的块进行升序排序，仍然相同则根据 $tim$ 的大小升序排序。请注意，再待修莫队中，块长为 $n^{\frac{2}{3}}$。最终时间复杂度为 $O(n^{\frac{3}{5}})$.

例题：数颜色

树上莫队

如果有一个问题和普通莫队要求的内容类似，但是查询的是树上一条链的结果，就可以用树上莫队。

首先，我们求出这棵树的欧拉序（即，一个点进出分别会被继续一次，记进的时间戳为 $in_u$，出的时间戳为 $out_u$）。对于一次询问 $[u,v]$，不妨令 $in_u \le in_v$，如果 $out_u \ge out_v$，即点 $v$ 是点 $u$ 子树上的点，则 $(u,v)$ 链上的点是欧拉序中 $[in_u,in_v]$ 区间内所有出现次数为奇数的点，否则 $(u,v)$ 链上的点是欧拉序中 $[out_u,in_v]$ 区间内所有出现次数为奇数的点，再加上 $\operatorname{lca}(u,v)$。如此以来，我们就把树上的问题转化成了区间查询，再利用普通莫队的方法即可，只是对数的加减改成了对某点出现次数奇偶性的更改，若为奇数，则加入该点，否则删除该点。令块长为 $\sqrt n$，则时间复杂度为 $O(n\sqrt n)$​。

例题：树上莫队模板题

可并堆/左偏树

左偏树是一种堆的实现，他保证了对于任意一点，左链的长度始终大于右链，因此在合并过程中，只要我们一直考虑右链，即，若要合并的两个小根堆堆顶为 $x,y$，若 $x<y$ 就用 $x$ 的右儿子与 $y$ 继续合并，反之用 $y$ 的右儿子和 $x$ 继续合并，如此一来，就能保证合并的时间复杂度为 $O(\log n)$​。

例题：【模板】左偏树/可并堆

笛卡尔树

笛卡尔树是一种中序遍历与数列相同，且具有堆结构的一种二叉树，可以把数列问题转化到树上问题。我们可以用一个单调栈来建立笛卡尔树，例如，对于一个大根堆的笛卡尔树，可以通过如下代码建立：

stack<int> st;
for(int i=1;i<=n;i++){
    while(!st.empty()&&a[i]>a[st.top()]){ls[i]=st.top();st.pop();}
    if(!st.empty()) rs[st.top()]=i;
    st.push(i);
}

例题：Add One 2

代码

树状数组

#define lowbit(x) ((x)&(-x))
ll tr[N];
void add(int x,ll k){while(x<=n){tr[x]+=k;x+=lowbit(x);}}
ll query(int x){ll ret=0;while(x){ret+=tr[x];x-=lowbit(x);}return ret;}

线段树

struct SegmentTree{
    #define ls ((u)<<1)
    #define rs ((u)<<1|1)
    struct node{

        int l,r;
    }tr[4*N];
    void init_lazy(int u){

    }
    void union_lazy(int fa,int u){

    }
    void cal_lazy(int u){

    }
    void pushdown(int u){
        if(){
            cal_lazy(u);
            if(tr[u].l!=tr[u].r){
                union_lazy(u,ls);
                union_lazy(u,rs);
            }
            init_lazy(u);
        }
    }
    void pushup(int u){
        pushdown(ls);pushdown(rs);

    }
    void build(int u,int l,int r,ll *A){
        tr[u].l=l;tr[u].r=r;
        init_lazy(u);
        if(l==r){

        }
        else{
            int mid=(l+r)>>1;
            build(ls,l,mid,A);build(rs,mid+1,r,A);
            pushup(u);
        }
    }
    void change(int u,int L,int R,ll k,int opt){
        pushdown(u);
        if(tr[u].r<=R&&tr[u].l>=L){
            tr[u].lazy[opt]=k;
            return;
        }
        int mid=(tr[u].l+tr[u].r)/2;
        if(R<=mid){change(ls,L,R,k,opt);}
        else if(L>mid){change(rs,L,R,k,opt);}
        else{change(ls,L,R,k,opt);change(rs,L,R,k,opt);}
        pushup(u);
    }
    ll query(int u,int L,int R){
        pushdown(u);
        if(tr[u].r<=R&&tr[u].l>=L) return ;
        int mid=(tr[u].l+tr[u].r)/2;
        if(R<=mid) return query(ls,L,R);
        else if(L>mid) return query(rs,L,R);
        else return query(ls,L,R)+query(rs,L,R);
    }
}ST;

李超线段树

struct Line{
    ll k,b;
    ll val(ll x){return k*x+b;}
    Line(ll kk=0,ll bb=0){
        k=kk;b=bb;
    }
};
struct Lichao_SegmentTree{
    const ll LCinf=1e18;
    #define ls ((u)<<1)
    #define rs ((u)<<1|1)
    ll crossX(Line i,Line j){
        return (j.b-i.b)/(i.k-j.k);
    }
    struct node{
        Line lin;
        int l,r;
        bool has_lin,vis;
    }tr[4*N];
    void build(int u,int l,int r){
        tr[u].l=l;tr[u].r=r;
        tr[u].vis=tr[u].has_lin=0;
        if(l==r){
            return;
        }
        else{
            int mid=(l+r)>>1;
            build(ls,l,mid);build(rs,mid+1,r);
        }
    }
    void insert(int u,int L,int R,Line x){
        if(tr[u].l==0&&tr[u].r==0) return;
        if(tr[u].r<=R&&tr[u].l>=L){
            if(!tr[u].has_lin){
                tr[u].has_lin=1;
                tr[u].lin=x;
                return;
            }
            if(tr[u].lin.val(tr[u].l)>=x.val(tr[u].l)&&tr[u].lin.val(tr[u].r)>=x.val(tr[u].r)) return;
            if(tr[u].lin.val(tr[u].l)<=x.val(tr[u].l)&&tr[u].lin.val(tr[u].r)<=x.val(tr[u].r)){tr[u].lin=x;return;}
            int mid=(tr[u].l+tr[u].r)/2;
            if(crossX(tr[u].lin,x)<=mid){
                if(x.k<tr[u].lin.k) insert(ls,L,R,x);
                else{insert(ls,L,R,tr[u].lin);tr[u].lin=x;}
            }
            else{
                if(x.k>tr[u].lin.k) insert(rs,L,R,x);
                else{insert(rs,L,R,tr[u].lin);tr[u].lin=x;}
            }
            return;
        }
        int mid=(tr[u].l+tr[u].r)/2;
        if(R<=mid){insert(ls,L,R,x);}
        else if(L>mid){insert(rs,L,R,x);}
        else{insert(ls,L,R,x);insert(rs,L,R,x);}
    }
    ll query(int u,int x){
        if(!tr[u].has_lin) return -LCinf;
        if(tr[u].l==tr[u].r) return tr[u].lin.val(x);
        int mid=(tr[u].l+tr[u].r)/2;
        if(x<=mid) return max(tr[u].lin.val(x),query(ls,x));
        else return max(tr[u].lin.val(x),query(rs,x));
    }
}ST;

Splay

struct SplayTree{
    struct Splay_Tree{
        int son[2],fa,cnt,val,siz,tag;
    }tree[N];
    int root,cnt;
    const int inf=2147483647;
    void pushup(int u){
        tree[u].siz=tree[tree[u].son[0]].siz+tree[tree[u].son[1]].siz+tree[u].cnt;
    }
    void pushdown(int x){
        if(tree[x].tag){

        }
    }
    int build(int l,int r,int fa){//根据数组 a 建树并返回根结点,如果不需要建树,请删除这一段代码
        if(l>r) return 0;
        int v=++cnt;
        tree[v].fa=fa;
        tree[v].cnt=1;
        int mid=(l+r)>>1;
        //tree[v].val=a[mid];
        tree[v].son[0]=build(l,mid-1,v);
        tree[v].son[1]=build(mid+1,r,v);
        pushup(v);
        return v;
    }
    bool check(int u){
        return tree[tree[u].fa].son[1]==u;
    }
    void rotate(int u){//单次旋转操作
        int fa=tree[u].fa;
        int ffa=tree[fa].fa;
        pushdown(fa);pushdown(u);
        int k=check(u);
        tree[ffa].son[check(fa)]=u;tree[u].fa=ffa;
        tree[fa].son[k]=tree[u].son[k^1];tree[tree[u].son[k^1]].fa=fa;
        tree[u].son[k^1]=fa;tree[fa].fa=u;
        pushup(fa);pushup(u);
    }
    void splay(int u,int goal){//将 u 向上旋转直至父亲为 goal(goal=0->旋到根)
        while(tree[u].fa!=goal){
            int fa=tree[u].fa;
            int ffa=tree[fa].fa;
            pushdown(fa);pushdown(u);
            if(ffa!=goal){
                if(check(u)==check(fa)) rotate(fa);
                else rotate(u);
            }
            rotate(u);
        }
        if(!goal) root=u;
    }
    void insert(int x){//插入一个数
        int u=root,fa=0;
        while(tree[u].val!=x&&u){
            pushdown(u);
            fa=u;
            u=tree[u].son[x>tree[u].val];
        }
        if(u) tree[u].cnt++;
        else{
            u=++cnt;
            if(fa) tree[fa].son[x>tree[fa].val]=u;
            tree[u].fa=fa;tree[u].val=x;
            tree[u].cnt=tree[u].siz=1;
        }
        splay(u,0);
    }
    void find(int x){//寻找一个数
        int u=root;
        while(x!=tree[u].val&&tree[u].son[x>tree[u].val]){
            pushdown(u);
            u=tree[u].son[x>tree[u].val];
        }
        splay(u,0);
    }
    void del(int x){//删除一个数
        int l=frne(x,0);
        int r=frne(x,1);
        splay(l,0);splay(r,l);
        int tmp=tree[r].son[0];
        if(tree[tmp].cnt>1){
            tree[tmp].cnt--;
            splay(tmp,0);
        }
        else tree[r].son[0]=0;
    }
    int query(int rk){//查找排名为 rk 的数
        int u=root;
        pushdown(u);
        while(1){
            if(tree[tree[u].son[0]].siz>=rk){
                u=tree[u].son[0];
            }
            else if(tree[tree[u].son[0]].siz+tree[u].cnt>=rk) return u;
            else{
                rk-=tree[tree[u].son[0]].siz+tree[u].cnt;
                u=tree[u].son[1];
            }
            pushdown(u);
        }
    }
    int frne(int x,int opt){//求 x 的前驱/后继
        find(x);
        int u=root;
        if((!opt&&tree[u].val<x)||(opt&&tree[u].val>x)) return u;
        pushdown(u);
        u=tree[u].son[opt];
        while(tree[u].son[opt^1]){
            pushdown(u);
            u=tree[u].son[opt^1];
        }
        return u;
    }
}Splay;
//建议在操作开始前使用这两行代码来减少特判
//Splay.insert(-inf);Splay.insert(inf);

普通莫队

struct node{
    int l,r,id,ans;
}q[N];
bool cmp1(node i,node j){
    if(i.l/block==j.l/block) return i.r<j.r;
    else return i.l/block<j.l/block;
}
bool cmp2(node i,node j){
    return i.id<j.id;
}
void add(int k){
    //do something
}
void del(int k){
    //do something
}
void solve(){
    scanf("%d%d",&n,&m);block=sqrt(n);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+1+m,cmp1);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        while(r<q[i].r) add(++r);
        while(r>q[i].r) del(r--);
        while(l<q[i].l) del(l++);
        while(l>q[i].l) add(--l);
        //do something
    }
    sort(q+1,q+1+m,cmp2);
    for(int i=1;i<=m;i++){
        printf("%d\n",q[i].ans);
    }
}

带修莫队

int cntq,cntr,block;
char op[5];
struct node{
    int l,r,tim,id,ans;
}q[N];
struct node2{
    int pos,col;
}R[N];
bool cmp(node i,node j){
    if(i.l/block!=j.l/block) return i.l/block<j.l/block;
    if(i.r/block!=j.r/block) return i.r/block<j.r/block;
    return i.tim<j.tim;
}
bool cmp2(node i,node j){
    return i.id<j.id;
}
void add(int k){
    //do something
}
void del(int k){
    //do something
}
void solve(){
    scanf("%d%d",&n,&m);block=pow(n,2.0/3.0);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        scanf("%s",op);
        if(op[0]=='Q'){
            cntq++;
            scanf("%d%d",&q[cntq].l,&q[cntq].r);
            q[cntq].id=cntq;q[cntq].tim=cntr;
        }
        else{
            cntr++;
            scanf("%d%d",&R[cntr].pos,&R[cntr].col);
        }
    }
    sort(q+1,q+1+cntq,cmp);
    int l=1,r=0,t=0;
    for(int i=1;i<=cntq;i++){
        while(r<q[i].r) add(++r);
        while(r>q[i].r) del(r--);
        while(l<q[i].l) del(l++);
        while(l>q[i].l) add(--l);
        while(t<q[i].tim){
            t++;
            if(R[t].pos>=q[i].l&&R[t].pos<=q[i].r) del(R[t].pos);
            swap(a[R[t].pos],R[t].col);
            if(R[t].pos>=q[i].l&&R[t].pos<=q[i].r) add(R[t].pos);
        }
        while(t>q[i].tim){
            if(R[t].pos>=q[i].l&&R[t].pos<=q[i].r) del(R[t].pos);
            swap(a[R[t].pos],R[t].col);
            if(R[t].pos>=q[i].l&&R[t].pos<=q[i].r) add(R[t].pos);
            t--;
        }
        q[i].ans=now;
    }
    sort(q+1,q+1+cntq,cmp2);
    for(int i=1;i<=cntq;i++){
        printf("%d\n",q[i].ans);
    }
}

树上莫队

struct node{
    int to,nxt;
}e[M];
int block,head[N],cnt,n,m,col[N];
void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int euler[N],in[N],out[N],cnte;
int fa[N][20],dep[N];
void dfs(int u,int f){
    euler[++cnte]=u;in[u]=cnte;
    fa[u][0]=f;dep[u]=dep[f]+1;
    for(int i=1;i<=19;i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==f) continue;
        dfs(v,u);
    }
    euler[++cnte]=u;out[u]=cnte;
}
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=19;i>=0;i--){
        if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    }
    if(u==v) return u;
    for(int i=19;i>=0;i--){
        if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0];
}
struct nodeModui{
    int l,r,id,ans,ex;
}q[N];
bool cmp1(nodeModui i,nodeModui j){
    if(i.l/block==j.l/block) return i.r<j.r;
    else return i.l/block<j.l/block;
}
bool cmp2(nodeModui i,nodeModui j){
    return i.id<j.id;
}
bool tag[N];
int tot[COL],now;
void work(int u){
    tag[u]^=1;
    if(tag[u]==1){
        //do something
    }
    else{
        //do something
    }
}
void MoDui(){
    sort(q+1,q+1+m,cmp1);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        while(r<q[i].r) work(euler[++r]);
        while(r>q[i].r) work(euler[r--]);
        while(l<q[i].l) work(euler[l++]);
        while(l>q[i].l) work(euler[--l]);
        if(q[i].ex){
            work(q[i].ex);
            q[i].ans=now;
            work(q[i].ex);
        }
        else{
            q[i].ans=now;
        }
    }
}
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&col[i]);
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(1,1);block=sqrt(2*n);
    scanf("%d",&m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        if(in[u]>in[v]) swap(u,v);
        if(out[u]>=out[v]){
            q[i].l=in[u];
            q[i].r=in[v];
            q[i].ex=0;
        }
        else{
            q[i].l=out[u];
            q[i].r=in[v];
            q[i].ex=lca(u,v);
        }
        q[i].id=i;
    }
    MoDui();
    sort(q+1,q+1+m,cmp2);
    for(int i=1;i<=m;i++){
        printf("%d\n",q[i].ans);
    }
}

左偏树/可并堆

int fa[N],dis[N],ls[N],rs[N];
int find(int x){
    return fa[x]==x?x:(fa[x]=find(fa[x]));
}
struct node{
    int id,val;
}a[N];
bool operator <(node i,node j){
    return i.val==j.val?i.id<j.id:i.val<j.val;
}
int merge(int x,int y){
    if(!x||!y) return x+y;
    if(a[y]<a[x]) swap(x,y);
    rs[x]=merge(rs[x],y);
    if(dis[rs[x]]>dis[ls[x]]) swap(rs[x],ls[x]);
    dis[x]=dis[rs[x]]+1;
    return x;
}

树上信息维护

树的 dfs 序

在二叉树中我们有前序，中序，后续。而对于一棵普通树，我们有三种常用的 dfs 序。

• dfs 序：第一次遍历一个点时把该点加入序列（上图的一个可能的 dfs 序为 1,4,2,5,7,6,3）。
  • dfs 序通常用于子树和树链操作类问题。
• 扩展 dfs 序：第一次遍历一个点时，以及遍历一个点的儿子前，把该点加入序列（上图的一个可能的扩展 dfs 序为 1,1,4,1,2,2,5,5,7,2,6,1,3）。
  • 对于两个点 $u,v$，其 LCA 就是 $[id_u,id_v]$ 区间中深度最低的点，容易发现这样的点一定是唯一的。可以通过维护一个 pair<depth,id> 来做到 $O(1)$ 查询 LCA。
  • 通过扩展 dfs 序，我们可以把 LCA 问题转化为 RMQ 问题；通过笛卡尔树，我们可以把 RMQ 问题转化为 LCA 问题，这有时候有益于思考与解决。
• 欧拉序：在第一次遍历一个点和这个点遍历完成后，把该点加入序列（上图的一个可能的欧拉序为 1,4,4,2,5,7,7,5,6,6,2,3,3,1）。
  • 欧拉序通常用于抵消前后的影响，例如树链上莫队，树链上亦或和。
  • 也可以利用欧拉序列维护信息，例如ETT（欧拉环游树）。

注意，不论在哪一种序列，$id_x$ 都表示点 $x$ 第一次进入序列对应的时间戳($dfn$)。

树上差分与树上倍增

树上差分与一维差分类似。对于树链上的差分，通常在点 $u,v,lca(u,v),fa_{lca(u,v)}$ 四点处打 tag。

树上倍增的思想即倍增求 lca 的影响，不多赘述。

例题：[JLOI2014]松鼠的新家

树链剖分/轻重链剖分

我的树链剖分学习笔记

树链剖分的核心思想就是将树分解成若干条链，同一条的 dfs 序是连续的，并保证一个点可以经过不超过 $\log n$ 条不同的链到达树根。在轻重链剖分中，我们通过优先走重儿子（子树大小最大的儿子）来做到这一点。

完成链分解后，我们可以利用一些数据结构来维护。对于子树的操作，其等价于对一段 dfs 序连续的点进行操作；对于链的操作，其等价于对 $\log n$ 段 dfs 序连续的点进行操作。

例题：

树上路径

[HAOI2015]树上操作

[LNOI2014]LCA

代码

树链剖分

int dep[N],son[N],siz[N],fa[N];
void dfs1(int u,int Fa){
    dep[u]=dep[Fa]+1;siz[u]=1;fa[u]=Fa;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==Fa) continue;
        dfs1(v,u);siz[u]+=siz[v];
        if(!son[u]||siz[v]>siz[son[u]]) son[u]=v;
    }
}
int top[N],dfn,id[N],idx[N];
void dfs2(int u,int Top){
    top[u]=Top;id[u]=++dfn;idx[dfn]=u;
    if(son[u]) dfs2(son[u],Top);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        //do something
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}