LuoguP 5327 [ZJOI 2019] 언어 선분 트 리 통합 + 트 리 체인 구 합

비교적 좋 은 데이터 구조 문제.    
$i $에 대해 우 리 는 $i $호 점 을 거 친 모든 경로 로 구 성 된 트 리 체인 의 합 을 구하 고 싶 습 니 다.    
나무 사슬 의 해 제 를 고려 한 전형 적 인 방법 은 $\ sum 입 니 다.{i=1}^{n} dep[i]-\sum_{i=2}^{n} dep[LCA(i,i-1)]$.    
모든 점 을 $dfs $순서대로 배열 해 야 합 니 다.  
그러면 이 문제 에서 우 리 는 DFS 순 서 를 바탕 으로 모든 점 에 동적 오픈 라인 트 리 를 만 듭 니 다.     
하나의 경 로 를 추가 하 는 것 은 $x, y $에 $(x, y) $를 추가 한 다음 $fa [lca] $에 이 네 개의 점 을 다시 삭제 하 는 것 입 니 다.    
아들 이 아버지 에 게 합병 할 때 직접 선분 나무 로 합병 하면 된다.  
pushup 시 유지 보수: $(s, t, f, si) $는 구간 의 가장 왼쪽 / 오른쪽 노드 번호, 구간 트 리 체인 의 길이, 그리고 잎 노드 가 열 린 통 을 표시 합 니 다.     
$RMQ - O (1) $로 $LCA $를 구하 면 $O (n \ log n) $를 할 수 있 습 니 다.  
코드: 

#include 
#include 
#include 
#include 
#define N 100009  
#define ll long long
#define pb push_back
#define lson s[x].ls 
#define rson s[x].rs   
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
ll ans; 
int n,m,edges,tim,tot;  
vectorADD[N],DEL[N];  
int hd[N],to[N<<1],nex[N<<1],rt[N]; 
int fa[N],dfn[N],seq[20][N<<1],dep[N],Log[N<<1]; 
void add(int u,int v) {
    nex[++edges]=hd[u]; 
    hd[u]=edges,to[edges]=v;  
}    
void dfs(int x,int ff) {
    dep[x]=dep[ff]+1;  
    fa[x]=ff,dfn[x]=++tim,seq[0][tim]=x;     
    for(int i=hd[x];i;i=nex[i]) {
        int y=to[i]; 
        if(y==ff) continue;  
        dfs(y,x);      
        seq[0][++tim]=x;          
    }
}
void RMQ() {
    Log[1]=0; 
    for(int i=2;i<=2*n;++i) {
        Log[i]=Log[i>>1]+1;  
    }
    for(int i=1;(1<y) swap(x,y);  
    int p=Log[y-x+1];     
    return dep[seq[p][x]]>1;   
    if(p<=mid)  {
        update(lson,l,mid,p,v);  
    }
    else {
        update(rson,mid+1,r,p,v); 
    }
    pushup(x);   
}
int merge(int l,int r,int x,int y) {
    if(!x||!y) {
        return x+y;  
    }   
    int now=++tot,mid=(l+r)>>1;    
    if(l==r) {
        s[now].si=s[x].si+s[y].si;   
        s[now].s=s[x].s|s[y].s;   
        s[now].t=s[x].t|s[y].t;  
        s[now].f=s[x].f|s[y].f;   
        return now;        
    }
    s[now].ls=merge(l,mid,s[x].ls,s[y].ls); 
    s[now].rs=merge(mid+1,r,s[x].rs,s[y].rs);  
    pushup(now); 
    return now;    
} 
void solve(int x,int ff) {
    for(int i=hd[x];i;i=nex[i]) {
        int y=to[i]; 
        if(y==ff) continue;  
        solve(y,x);  
        rt[x]=merge(1,n<<1,rt[x],rt[y]);  
    }     
    for(int i=0;i>1);   
    return 0;
}