트 리 체인 분할 템 플 릿 (점 권 기반, 변 권 기반)

트 리 체인 분할 은 데이터 구조 가 트 리 에서 의 홍보 이다. 사실은 트 리 hash 를 몇 개의 연속 적 인 구간 으로 한 다음 에 다른 데이터 구조 로 유지 하 는 것 은 트 리 에 대해 예비 처리 dfs 1 () 을 구 하 는 것 과 같다. fa, deep, size, son dfs 2 () 는 top, p 를 구 하 는 것 과 같다.
주의: 번 호 를 다시 매 긴 후 번호 구간 이 몇 개의 관건 적 인 배열 인지 주의해 야 합 니 다: int deep [maxn];int size[maxn]; int fa[maxn]; int p[maxn]; int son[maxn]; int fp[maxn]; int top[maxn];
나무 사슬 의 분할 은 점 권 을 바탕 으로 하고 변 권 을 바탕 으로 점 권 (hdu 3966) 을 바탕 으로 나무 에 있 는 점 에 다시 번 호 를 매 긴 다. p [u] 는 u 가 대응 하 는 위 치 는 변 권 (spoj 375) 을 바탕 으로 나무 에 있 는 변 에 다시 번 호 를 매 긴 다 는 것 을 나타 낸다. p [u] 는 u 와 아버지 노드 의 연결 변 의 위 치 를 나타 내 면 뿌리 결점 과 아버지 노드 의 연결 변 은 사용 할 수 없다.

const int maxn=10010;
using namespace std;

/*-----------------------------    ---------------------*/
struct node{
    int v,next;
}edges[maxn<<1];int tot,head[maxn],n;
inline void addedge(int u,int v){//       
    edges[tot].next=head[u];
    edges[tot].v=v;
    head[u]=tot++;
}
int deep[maxn],size[maxn],top[maxn],fa[maxn],p[maxn],son[maxn],fp[maxn];
//  ，   ，       ，    ，v                 (v     )，   ， p    
int pos;
void Init(){
    memset(son,-1,sizeof(son));
    memset(head,-1,sizeof(head));
    tot=pos=0;
}
void dfs1(int u,int pre,int d){//   dfs  fa，deep，size，son
    deep[u]=d;
    fa[u]=pre;
    size[u]=1;
    for(int i=head[u];i!=-1;i=edges[i].next){
        int v=edges[i].v;
        if(v!=pre){
            dfs1(v,u,d+1);
            size[u]+=size[v];
            if(son[u]==-1||size[son[u]]<size[v]) son[u]=v;
        }
    }
}
void getpos(int u,int sp){//   dfs  top p
    top[u]=sp;
    p[u]=pos++;
    fp[p[u]]=u;
    if(son[u]==-1) return ;
    getpos(son[u],sp);
    for(int i=head[u];i!=-1;i=edges[i].next){
        int v=edges[i].v;
        if(v!=son[u]&&v!=fa[u]) getpos(v,v);
    }
}

수정: 깊이 가 큰 체인 을 선택 할 때마다 수정 한 다음 에 u 를 LCA 에 언급 하여 f1 = = f2 까지 합 니 다.f1 = f2 후에 u, v 가 같은 체인 에 있다 는 것 을 설명 합 니 다. 1. 점 권 을 바탕 으로 할 때 u = = v 라 도 경로 (u, v) 의 모든 점 을 수정 해 야 합 니 다. 모든 점 은 트 리 의 번 호 를 대표 하기 때 문 입 니 다. 2. 변 권 을 바탕 으로 할 때 경로 (son [u], v) 의 변 을 수정 해 야 합 니 다. 각 점 v 의 위 치 는 v 가 아버지 노드 의 가장자리 에 있 는 번 호 를 표시 하기 때 문 입 니 다.
점 권 기반:

void change(int u,int v,int val){
    int f1=top[u],f2=top[v];
    while(f1!=f2){
        if(deep[f1]<deep[f2]){
            swap(f1,f2);
            swap(u,v);
        }
        add(p[f1],val);
        add(p[u]+1,-val);
        u=fa[f1];f1=top[u];
    }
    //  （u==v)   
    if(deep[u]>deep[v]) swap(u,v);
    add(p[u],val);
    add(p[v]+1,-val);
}

변 권 기반:

int find(int u,int v){
    int f1=top[u],f2=top[v];
    int ans=0;
    while(f1!=f2){
        if(dep[f1]<dep[f2]){
            swap(f1,f2);
            swap(u,v);
        }
        ans=max(ans,query(p[f1],p[u],1,pos-1,1));
        u=fa[f1];f1=top[u];
    }
    if(u==v) return ans;//   u==v   
    if(dep[u]>dep[v]) swap(u,v);
    return max(ans,query(p[son[u]],p[v],1,pos-1,1));
}