BOJ 13510 트리와 쿼리 1

ㅎㅇ! 오랜만에 글 쓴다.
사실 그동안 센트로이드 디컴퍼지션 짜다가 짜증나서 얼른 이 문제로 갈아 탔다.
각설하고, 트리와 쿼리 1을 푸는 방법을 알아보자.

선행지식: Heavy Light Decomposition
문제: BOJ13510

우선, HLD 문제 잘 푸는 사람이 이 글을 볼 리는 없다는 가정하에 글을 쓴다.

HLD를 배웠다면 HLD의 작동 메커니즘이 간선이 아닌, 노드 위주의 쿼리를 처리하는 것임을 알 수 있다.
그래서 그냥 HLD를 구현하는 것으론 부족하니 간선의 특성을 노드의 특성으로 바꿔주면 좋겠다는 생각을 했을 수도 있다.

간선의 가중치를 노드의 특성으로

간단하다. 노드에 연결된 어떠한 간선의 가중치를 노드의 각종 정보를 초기화할 때 같이 기록하면 되겠다. 여기서 어떠한은 무엇을 말할까? 이왕이면 각 노드들에 하나만 있으면 좋겠으니 노드에서 부모로 향하는 간선으로 하자.
(한 가지 주의할 점은, 루트 노드의 부모로의 간선의 가중치는 간선의 가중치가 될 수 없는 작은 값이어야 한다는 것이다.)

쿼리의 처리

트리에서 두 노드 간의 경로는 u->lca(u,v)->v임은 돌골렘도 아는 사실이다.
이 문제에서 답을 구할 때는 a->b의 경로와 b->a의 경로가 그 값이 같고, 분할된 두 경로를 통해 전체의 답을 쉽게 구할 수 있다.
따라서 경로 u->lca(u,v)->v를 u->lca(u,v) 와 v->lca(u,v) 의 경로로 분할하고 각각에 대한 해답을 통해 쉽게 구할 수 있다.

정답 코드

복붙은 돌골렘이 되는 지름길이다. HLD의 구현량이 많은 편이지만, 끝까지 인내하고 한 번쯤은 직접 구현해보길 바란다.

#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ppi=pair<int,pii>;

const int nmax = 100010;

#define fi first
#define se second

#define fastio do{ios::sync_with_stdio(0);cin.tie(0);}while(0)

#define radj(x) for(auto [nxt,wei]:adj[x])

int n,m;
vector<pii> adj[nmax];
vector<ppi> edge;
int seg[nmax<<2];
int w[nmax];
int d[nmax];
int v[nmax];
int sps[20][nmax];
int idx[nmax];
int rev[nmax];
int hld[nmax];

/*Maximum Segment Tree - begin*/
//One-Node Update
void su(int idx,int l,int r,int p,int x){
    if(l>p||r<p)return;
    if(l!=r){
        int mid=l+r>>1;
        su(idx<<1,l,mid,p,x);su((idx<<1)+1,mid+1,r,p,x);
        seg[idx]=max(seg[idx<<1],seg[(idx<<1)+1]);
        return;
    }
    seg[idx]=v[l]=x;
}
//Range Maximum Query
int sq(int idx,int l,int r,int s,int e){
    if(l>e||r<s)return 0;
    if(s<=l&&r<=e)return seg[idx];
    int mid=l+r>>1;
    return max(sq(idx<<1,l,mid,s,e),sq((idx<<1)+1,mid+1,r,s,e));
}
/*Maximum Segment Tree - end*/

//Lowest Common Ancestor
int lca(int u,int v){
    if(d[u]>d[v])swap(u,v);
    for(int i=19;i>=0;i--)if(d[v]-d[u]>=(1<<i))v=sps[i][v];
    if(u==v)return u;
    for(int i=19;i>=0;i--)if(sps[i][u]!=sps[i][v]){
        u=sps[i][u];v=sps[i][v];
    }
    return sps[0][u];
}

/*HLD - begin*/
//Init Weight, Depth, SparseTable
void dfs(int now){
    w[now]=1;
    radj(now)if(!w[nxt]){
        v[nxt]=wei;
        sps[0][nxt]=now;
        d[nxt]=d[now]+1;
        dfs(nxt);
        w[now]+=w[nxt];
    }
}
//DFS ordering
int dn;
void dfs2(int now){
    int cc=-1;
    idx[now]=++dn;
    rev[idx[now]]=now;
    radj(now)
        if(sps[0][nxt]==now&&(cc==-1||w[nxt]>w[cc]))
            cc=nxt;
    if(cc!=-1){
        hld[cc]=hld[now];
        dfs2(cc);
    }
    radj(now)if(sps[0][nxt]==now&&nxt!=cc){
        hld[nxt]=nxt;
        dfs2(nxt);
    }
}
//Update EdgeWeight
void hld_upd(int eidx,int x){
    if(d[edge[eidx].se.fi]>d[edge[eidx].se.se]){
        su(1,1,n,idx[edge[eidx].se.fi],x);
    }
    else{
        su(1,1,n,idx[edge[eidx].se.se],x);
    }
}
//Query_Divided / v is anc of u
int hld_hq(int u,int v){
    int r=0;
    while(hld[u]!=hld[v]){
        r=max(r,sq(1,1,n,idx[hld[u]],idx[u]));
        u=sps[0][hld[u]];
    }
    if(u!=v){
        r=max(r,sq(1,1,n,idx[v]+1,idx[u]));
    }
    return r;
}
//Query
int hld_query(int u,int v){
    int l=lca(u,v);
    return max(hld_hq(u,l),hld_hq(v,l));
}
/*HLD - end*/

//Main
int main(void){
    fastio;
    
    cin>>n;
    edge.resize(n-1);
    for(int i=1;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        edge[i-1]=ppi(c,pii(a,b));
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }
    
    dfs(1);dfs2(1);
    for(int i=1;i<20;i++){
        for(int j=1;j<=n;j++){
            sps[i][j]=sps[i-1][sps[i-1][j]];
        }
    }
    for(int i=0;i<n-1;i++){
        hld_upd(i,edge[i].fi);
    }
    
    cin>>m;
    while(m--){
        int x,a,b;
        cin>>x>>a>>b;
        if(x==1){
            edge[a-1].fi=b;
            hld_upd(a-1,b);
        }
        else{
            cout<<hld_query(a,b)<<"\n";
        }
    }
}