나무 사슬 분할 (2)

오전 에 트 리 체인 분할 모드 문 제 를 풀 었 습 니 다.............................................................................2. 두 점 경로 의 모든 가중치 에 한 개의 수 를 동시에 추가 하거나 줄인다.한 번 조회 의 정상 적 인 복잡 도 O (n), 한 번 변 경 된 복잡 도 O (n) 를 고려 하면 O (nm) 가 시간 을 초과 한 것 을 알 수 있다.O (mlog2n) 지나 갈 수 있 습 니 다.일부 데이터 구 조 를 사용 하 는 것 을 고려 하지만 분명히 이 라인 트 리 같은 것 은 불합리 하 다. 왜냐하면 그것 은 하나의 체인 이 아니 기 때문이다.그러나 우 리 는 한 그루 의 나 무 를 몇 개의 사슬 로 베 어 연결 하여 긴 사슬 을 만 들 수 있다.이것 이 바로 나무 사슬 분할 의 기본 원리 다.절개 방법: 경중 변 구분: size [x] 는 x 를 서브 트 리 로 하 는 노드 개수 로 정의 합 니 다.중 아들: 현재 노드 에서 size 가 가장 큰 아들 (size 가 같 으 면 아무 거나 연결).무 거 운 변: 현재 노드 와 무 거 운 아이의 변 을 연결 합 니 다.가 벼 운 쪽: 현재 노드 와 무 거 운 아 이 를 제외 한 쪽 을 연결 합 니 다.사용 할 변 수 는 다음 과 같 습 니 다.

    tim//   
    size[]//     size 
    son[]//          
    fa[]//         
    dep[]//       
    top[]//        (         )
    tid[]//       
    Rank[]//           

나무 사슬 을 나 눌 때 먼저 우 리 는 모든 노드 의 size 를 확정 하여 무 거 운 아들 을 확정 한 다음 에 무 거 운 변 으로 연결 해 야 한다.그 후에 우 리 는 다시 무 거 운 가장 자 리 를 연결 하여 무 거 운 사슬 로 만 들 었 다.이 과정 은 양쪽 dfs 가 필요 합 니 다.

void dfs1(int rt,int f,int depth){//     
    fa[rt]=f;//    
    dep[rt]=depth;//    
    size[rt]=1;//size    1(     )
    for(int i=head[rt];~i;i=edge[i].next){//     
        int v=edge[i].to;
        if(v!=f){//      
            dfs1(v,rt,depth+1);
            size[rt]+=size[v];//             size
            if(son[rt]==-1||size[son[rt]]<size[v])//       ||size        
                son[rt]=v;
        }
    }   
}

void dfs2(int rt,int tp){//tp    
    top[rt]=tp;
    tid[rt]=++tim;
    Rank[tim]=rt;
    if(son[rt]==-1)return;
    dfs2(son[rt],tp);//     ，    
    for(int i=head[rt];~i;i=edge[i].next){
        int v=edge[i].to;
        if(v!=fa[rt]&&v!=son[rt])
            dfs2(v,v);
    }
}

tid & & Rank - 개인 적 으로 가장 이해 하기 어 려 운 나무 사슬 의 일부 나무 사슬 의 분할 은 시간 에 따라 전체 나 무 를 만 드 는 것 이 라 고 생각 합 니 다. 즉, 우리 가 노드 가 현재 체인 에 있 는 위 치 를 찾 으 려 고 할 때 tid 배열 은 중요 한 역할 을 합 니 다. tid [x] = tim 이 고 tim 이 대응 하 는 것 은 현재 체인 의 위치 이기 때 문 입 니 다.Rank 배열 은 현재 시각 에 대응 하 는 노드 입 니 다.그래서: x = Rank [tid [x]];이 를 이해 한 후에 우 리 는 tid 로 특정한 노드 에 대응 하 는 전체 체인 의 위 치 를 찾 을 수 있 고 Rank 으로 특정한 위치 에 대응 하 는 나무의 어느 노드 를 찾 을 수 있다. 그러면 전체 나 무 는 철저하게 체인 으로 전환 할 수 있다.그러나 어떤 것들 은 나무 사슬 의 분할 에 있어 서 당연 하 다 고 생각 할 수 없다. 예 를 들 어 LCA 라 는 것 이 있다. 처음에 나 는 나무의 두 가지 경로 의 소유권 치 를 바 꾸 는 것 이 순진 하 다 고 생각 했다. 그러면 이렇게 할 수 있다. 그들의 LCA 를 찾 아 한 경 로 를 두 개의 체인 으로 나 누 어 바 꾸 고 선분 나무 로 유지 할 수 있다.지금 생각해 보면........................................................................................그리고 LCA...............................................................................그 러 니까...(적어도 이 문 제 는 자신 을 함정 에 빠 뜨리 는 것 이다)
경로 구간 조작 시 dep [] 로 기괴 한 조작 을 하 세 요!
구간 수정 사고: x, y 간 의 경 로 를 구간 수정 합 니 다.

void chage(){
while(x，y       )｛
    dep[top[x]]<dep[top[y]]?swap(x,y):1；
     x---top[x]        ；
    x=fa[top[x]];
    ｝
     x---y        。
}

이 문제 의 코드 를 보 낼 때 가 되 었 습 니 다..........................................................................

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 50005
#define lc rt<<1,l,mid
#define rc rt<<1|1,mid+1,r
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
int n,m,p,cnt=0,tim=0;
int son[N],dep[N],Rank[N],size[N],tid[N],fa[N],head[N<<1],w[N],top[N],sum[N<<2],lazy[N<<2];
struct Edge{
    int next,to;
}edge[N<<1];
void save(int u,int v){
    edge[cnt].next=head[u];
    edge[cnt].to=v;
    head[u]=cnt++;
}
void dfs1(int rt,int f,int depth){
    fa[rt]=f;
    dep[rt]=depth;
    size[rt]=1;
    for(int i=head[rt];~i;i=edge[i].next){
        int v=edge[i].to;
        if(v!=f){
            dfs1(v,rt,depth+1);
            size[rt]+=size[v];
            if(son[rt]==-1||size[son[rt]]<size[v])
                son[rt]=v;
        }
    }
}
void dfs2(int rt,int tp){
    top[rt]=tp;
    tid[rt]=++tim;
    Rank[tim]=rt;
    if(son[rt]==-1)return;
    dfs2(son[rt],tp);
    for(int i=head[rt];~i;i=edge[i].next){
        int v=edge[i].to;
        if(v!=son[rt]&&v!=fa[rt])
            dfs2(v,v);
    }
}
//     
void build(int rt,int l,int r){
    lazy[rt]=0;
    if(l==r){
        sum[rt]=w[Rank[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(lc);
    build(rc);
}
void pushdown(int rt){
    if(lazy[rt]){
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        sum[rt<<1]+=lazy[rt];
        sum[rt<<1|1]+=lazy[rt];
        lazy[rt]=0;
    }
}
void modify(int rt,int l,int r,int lm,int rm,int modi){
    if(l>rm||r<lm)return;
    if(l>=lm&&r<=rm){
        lazy[rt]+=modi;
        sum[rt]+=modi*(r-l+1);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(rt);
    if(mid>=lm)modify(lc,lm,rm,modi);
    if(mid<rm)modify(rc,lm,rm,modi);
}
void Change(int x,int y,int val)  //           
{  
    while(top[x]!=top[y])  
    {  
        if(dep[top[x]]<dep[top[y]]) swap(x,y);  
        modify(1,1,n,tid[top[x]],tid[x],val);    
        x=fa[top[x]];  
    }  
    if(dep[x]>dep[y]) swap(x,y);  
    modify(1,1,n,tid[x],tid[y],val);  
}  
int query(int rt,int l,int r,int q){
    if(l==r)return sum[rt];
    int mid=(l+r)>>1;
    pushdown(rt);
    int ans=0;
    if(mid>=q)ans=query(lc,q);
    if(mid<q)ans=query(rc,q);
    return ans;
}
int main (){
    while(~scanf("%d%d%d",&n,&m,&p)){
        memset(head,-1,sizeof(head));
        memset(edge,0,sizeof(edge));
        cnt=tim=0;
        memset(son,-1,sizeof(son));
        for(int i=1;i<=n;i++)
            scanf("%d",&w[i]);
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            save(u,v);save(v,u);
        }
        dfs1(1,0,0);
        dfs2(1,1);
        build(1,1,n);
        for(int i=1;i<=p;i++){
            char c[5];
            scanf("%s",c);
            if(c[0]=='Q'){
                int q;
                scanf("%d",&q);
                printf("%d
",query(1,1,n,tid[q]));
            }
            else {
                int c1,c2,cg;
                scanf("%d%d%d",&c1,&c2,&cg);
                if(c[0]=='D')
                    Change(c1,c2,-cg);
                else 
                    Change(c1,c2,cg);
            }
        }
    }
    return 0;
}

이로써 간단 한 나무 사슬 분할 모형 문제 분석 이 완료 되 었 습 니 다!'간단 하 다' 는 단 어 는 '모형 문제' 를 수식 하 는 것 이지 나무 사슬 로 나 누 는 것 이 아 닙 니 다. (엄숙 한 얼굴)