这题并不难想，但是很难写。

首先先转化为开区间，然后一个就是挂左链，一个是挂右链。

然后变成了一个点与左链上挂的点的距离的问题。

然后就分讨吧！

此处省略一万字。

写完之后，编译了一下程序，电脑死机了。

然后发现自己CMLE了。(CMLE，即编译器内存超限）

原因是在c++11标准下struct内二维数组开太大了，过了一会发现是g++版本太低的锅，然而uoj版本也很低。

就不得不套上了一个诡异的东西，变长了也变慢了，可是终于能过编译了。

uoj 暂时代码长度rank 倒1,运行时间rank 倒2，惨。

#include 
    
     using namespace std;namespace Fastio{    const int BUFF=7e5;    char ch[BUFF],*l=ch,*r=ch;    char gc(){        if (l==r) l=ch,r=l+fread(ch,1,BUFF,stdin);        if (l==r) return EOF;        return *(l++);    }    void read(int &x) {        x = 0;        char ch = gc();        while(!isdigit(ch)) ch = gc();        while(isdigit(ch)) x = x * 10 + ch - '0', ch = gc();    }};using namespace Fastio;namespace container{    template
     
          class myarray{        struct period{            T a[BLOCK_SIZE];            period* ne=NULL;            period(){            }            period(const T &v){                fill(a,a+BLOCK_SIZE,v);            }        };        period *Be;        size_t Sz;        class iterator{            period *ip;            size_t pos;            myarray *po;        public:            typedef random_access_iterator_tag iterator_category;            typedef T value_type;            typedef T* pointer;            typedef T& reference;            typedef ptrdiff_t difference_type;            iterator():ip(nullptr),pos(0),po(nullptr){            }            iterator(const iterator &it){                (*this)=it;            }            iterator(period * const &ip,const size_t &pos,myarray * const &po):ip(ip),pos(pos),po(po){            }            bool operator !=(const iterator &it) const{                return ip!=it.ip||pos!=it.pos;            }            bool operator ==(const iterator &it) const{                return ip==it.ip&&pos==it.pos;            }            iterator operator ++(){                if (++pos==BLOCK_SIZE&&ip->ne!=NULL){                    ip=ip->ne;                    pos=0;                }                return *this;            }            const iterator operator ++(int){                iterator tmp(*this);                if (++pos==BLOCK_SIZE&&ip->ne!=NULL){                    ip=ip->ne;                    pos=0;                }                return tmp;            }            iterator operator --(){                if (pos){                    --pos;                    return (*this);                }                period *tBe=po->Be;                while (tBe->ne!=ip) tBe=tBe->ne;                ip=tBe;                pos=BLOCK_SIZE-1;                return (*this);            }            const iterator operator --(int){                iterator tmp(*this);                if (pos){                    --pos;                    return tmp;                }                period *tBe=po->Be;                while (tBe->ne!=ip) tBe=tBe->ne;                ip=tBe;                pos=BLOCK_SIZE-1;                return tmp;            }            iterator operator +(const size_t &len) const{                //ip!=NULL BUG                if (BLOCK_SIZE>pos+len) return iterator(ip,pos+len,po);                size_t tmp=len-(BLOCK_SIZE-1-pos);                if (ip->ne==NULL) return iterator(ip,BLOCK_SIZE,po);                period *tip=ip->ne;                while (tmp>BLOCK_SIZE){                    if (tip->ne==NULL) return iterator(tip,BLOCK_SIZE,po);                    tip=tip->ne;                    tmp-=BLOCK_SIZE;                }                return iterator(tip,tmp-1,po);            }            iterator operator +=(const size_t &len){                return ((*this)=(*this)+len);            }            size_t operator -(const iterator &it) const{                //only                if (ip==it.ip) return pos-it.pos;                period *tmp=it.ip->ne;                size_t ret=BLOCK_SIZE-it.pos;                while (tmp!=ip){                    ret+=BLOCK_SIZE;                    tmp=tmp->ne;                }                return ret+pos;            }            iterator operator -(const size_t &len) const{                return (po->begin()+((*this)-(po->begin())-len));            }            iterator operator -=(const size_t &len){                return ((*this)=(*this)-len);            }            bool operator <(const iterator &it) const{                //same father                return ((*this)-po->begin())<(it-(po->begin()));            }            bool operator <=(const iterator &it) const{                //same father                return ((*this)-po->begin())<=(it-(po->begin()));            }            T & operator *() const{                return ip->a[pos];            }        };    public:        typedef T value_type;        typedef T& reference;        typedef const T& const_reference;        typedef size_t size_type;        myarray(){            Be=NULL;            Sz=0;        }        myarray(const size_t &sz){            construct(sz);        }        myarray(const size_t &sz,const T &v){            construct(sz,v);        }        ~myarray(){            myfree(Be);        }        myarray(const myarray &rhs){            if (this==&rhs) return;            construct(rhs.size());            auto j=begin();            for (auto it=rhs.begin(); it!=rhs.end(); ++it) *(j++)=(*it);        }        myarray(const initializer_list
      
        &args){            construct(args.size());            auto j=begin();            for (auto it=args.begin(); it!=args.end(); ++it) *(j++)=(*it);        }        myarray& operator =(const myarray &rhs){            if (this==&rhs) return (*this);            myfree(Be);            construct(rhs.size());            auto j=begin();            for (auto it=rhs.begin(); it!=rhs.end(); ++it) *(j++)=(*it);            return *this;        }        void myfree(period * const &Be){            period *tBe=Be,*tmp;            while (tBe!=NULL){                tmp=tBe->ne;                delete tBe;                tBe=tmp;            }        }        void construct(const size_t &sz){            Be=new period();//slow but safe            Sz=sz;            size_t tSz=sz;            period *tBe=Be;            while (tSz>BLOCK_SIZE){                tBe=(tBe->ne=new period);                tSz-=BLOCK_SIZE;            }        }        void construct(const size_t &sz,const T &v){            Be=new period(v);            Sz=sz;            size_t tSz=sz;            period *tBe=Be;            while (tSz>BLOCK_SIZE){                tBe=(tBe->ne=new period);                tSz-=BLOCK_SIZE;            }        }        iterator begin() const{            return iterator(Be,0,(myarray*)this);        }        iterator end() const{            //Slow And Dangerous            if (Be==NULL) return iterator(NULL,0,(myarray*)this);            period *tBe=Be;            while (tBe->ne!=NULL) tBe=tBe->ne;            return iterator(tBe,((int)Sz-1)%(int)BLOCK_SIZE+1,(myarray*)this);        }        void push_back(const T &v){            if (Be==NULL){                Be=new period;                Be->a[Sz++]=v;                return;            }            period *tBe=Be;            while (tBe->ne!=NULL) tBe=tBe->ne;            size_t tSz=(Sz++)%BLOCK_SIZE;            if (tSz==0) tBe=(tBe->ne=new period);            tBe->a[tSz]=v;        }        void pop_back(){            if ((--Sz)%BLOCK_SIZE) return;            if (Sz==0){                delete Be;                Be=NULL;                return;            }            period *tBe=Be;            while (tBe->ne->ne!=NULL) tBe=tBe->ne;            delete tBe->ne;            tBe->ne=NULL;        }        T& operator [](const size_t &pos) const{            size_t tpos=pos;            for (period* i=Be; i!=NULL; i=i->ne)                if (tpos
       
        a[tpos];                else tpos-=BLOCK_SIZE;            throw;        }        T& front() const{            //unusual            return Be->a[0];        }        T& back() const{            return *(--end());        }        size_t size() const{            return Sz;        }        bool empty() const{            return Sz==0;        }        template
        
                 struct iterator_traits{            typedef typename U::value_type value_type;            typedef typename U::iterator_category iterator_category;            typedef typename U::difference_type difference_type;            typedef typename U::pointer pointer;            typedef typename U::reference reference;        };    };}template
         
          using arr=container::myarray
          
           ;typedef long long ll;typedef pair
           
             p;const int N=200005;int nodenum,fa[N*2][20];int son[N*2][2];int dep[N*2];int clk,dfn[N*2],en[N*2];void Rebuild(){ for (int j=1; j<=17; ++j) for (int i=1; i<=nodenum; ++i) fa[i][j]=fa[fa[i][j-1]][j-1];}int upto(const int &x,const int &y){ int tmp=x; int dis=dep[tmp]-dep[y]-1; for (int j=17; j>=0; --j) if ((dis>>j)&1) tmp=fa[tmp][j]; return tmp;}bool inrange(const int &x){ return x>=1&&x<=nodenum;}int Getlca(int x,int y){ if (!inrange(x)) return 0; if (!inrange(y)) return 0; if (dep[x]>dep[y]) swap(x,y); for (int j=17; j>=0; --j) if (fa[y][j]&&dep[x]<=dep[fa[y][j]]) y=fa[y][j]; if (x==y) return x; for (int j=17; j>=0; --j) if (fa[x][j]!=fa[y][j]){ x=fa[x][j]; y=fa[y][j]; } return fa[x][0];}p operator +(const p &A,const p &B){ return {A.first+B.first,A.second+B.second};}namespace Pre{ int tim,n,mid[N],trans[N*2]; void Divide(int x,int l,int r){ //cerr<<"Divide"<
            
             <<" "<
             
              <<" "<
              
               <
               
                 sum[N*2]; line(){ for (int i=1; i
                
                 (1); } void Ups(){ for (int i=1; i<=nodenum; ++i){ p tmp=sum[i][0]; sum[i]=arr
                 
                  (18); sum[i][0]=tmp; } } void Append(int x){ sum[x][0]=p({dep[x],1}); } void Rebuild(){ for (int j=1; j<=17; ++j) for (int i=1; i<=nodenum; ++i){ int faf=fa[i][j-1];//grand father if (!faf) continue; sum[i][j]=sum[i][j-1]+sum[faf][j-1]; } } p cat_chain(const int &x,const int &y){ int tmp=x; int dis=dep[tmp]-dep[y]; p ret=p({0ll,0}); for (int j=17; j>=0; --j) if ((dis>>j)&1){ ret=ret+sum[tmp][j]; tmp=fa[tmp][j]; } return ret; } bool is_child(const int &a,const int &b){ //a==b 1 return dfn[b]<=dfn[a]&&en[a]<=en[b]; } bool linear_relative_in_order(const int &a,const int &b,const int &c){ return is_child(a,b)&&is_child(b,c); } ll Downchain(int x,int top,int y,int d){ //cerr<<"Downchain"<
                  
                   <<" "<
                   
                    <<" "<
                    
                     <
                     
                      Pre::n) return 0; int ignore_pos=Getlca(x,y); //cerr<<"IGP"<
                      
                       <
                       
                        Pre::n||r<1||r>Pre::n?0:Getlca(l,r)); //cerr<<"lca"<
                        
                         <