BOJ 5916 - 농장 관리

문제 링크 : www.acmicpc.net/problem/5916

문제 태그

HLD ,segment tree lazy propagation

문제 풀이

문제를 보자... 1번 트리다. 2번 쿼리가 주어진다. 3번 그 쿼리가 경로 쿼리이다.... 아무리 봐도 이 문제는 HLD를 사용하는 문제라고 밖에는 생각이 들지 않는다. 경로에 모두 하나씩 심기 때문에 segment tree part에서 lazy propagation을 같이 섞어주면 문제를 해결할 수 있을 것 처럼 보인다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ll;
typedef pair<ll,ll> pii;
#define ff first
#define ss second
#define eb emplace_back
#define pb push_back
 
ll n;
ll par[101010];
ll vis[101010];
ll dep[101010];
ll sz[101010];
ll in[101010];
ll out[101011];
ll top[101010];
vector<ll> dv[101010];
vector<ll> v[101010];
 
void dfs1(ll x){
    sz[x]=1;
    for(auto n:v[x]){
        if(sz[n]) continue;
        dep[n]=dep[x]+1;
        par[n]=x;
        dfs1(n);
        sz[x]+=sz[n];
        dv[x].push_back(n);
        if(sz[n]>sz[dv[x][0]]) swap(dv[x][0],dv[x].back());
    }
}
 
ll np;
void dfs2(ll x){
    np++;
    in[x]=np;
    for(auto k:dv[x]){
        if(dv[x][0]==k) top[k]=top[x];
        else top[k]=k;
        dfs2(k);
    }
    out[x]=np;
}
 
struct node{
    ll val,lazp;
};
 
ll arr[101010];
node tree[500505];
 
void laz(ll s,ll e,ll nod){
    if(tree[nod].lazp!=0){
        tree[nod].val=(tree[nod].val+(e-s+1)*tree[nod].lazp);
        if(s!=e){
            tree[nod*2].lazp=(tree[nod*2].lazp+tree[nod].lazp);
            tree[nod*2+1].lazp=(tree[nod*2+1].lazp+tree[nod].lazp);
        }
        tree[nod].lazp=0;
    }
}
 
ll qpl(ll l,ll r,ll v,ll s,ll e,ll nod){
    laz(s,e,nod);
    if(r<s||e<l) return tree[nod].val;
    if(l<=s&&e<=r){
        tree[nod].lazp=v;
        laz(s,e,nod);
        return tree[nod].val;
    }
    return tree[nod].val=(qpl(l,r,v,s,(s+e)/2,nod*2)+qpl(l,r,v,(s+e)/2+1,e,nod*2+1));
}
 
ll qsol(ll l,ll r,ll s,ll e,ll nod){
    laz(s,e,nod);
    if(r<s||e<l) return 0;
    if(l<=s&&e<=r) return tree[nod].val;
    return qsol(l,r,s,(s+e)/2,nod*2)+qsol(l,r,(s+e)/2+1,e,nod*2+1);
}
 
void ppl(ll a,ll b,ll val){
    while(top[a]!=top[b]){
        if(dep[top[a]] > dep[top[b]]) swap(a, b);
        ll x=top[b];
        qpl(in[x],in[b],val,1,n,1);
        b=par[x];
    }
    if(dep[a] > dep[b]) swap(a, b);
    qpl(in[a]+1,in[b],val,1,n,1);
}
 
ll psol(ll a,ll b){
    ll ans = 0;
    while(top[a]!=top[b]){
        if(dep[top[a]] > dep[top[b]]) swap(a, b);
        ll x=top[b];
        ans+=qsol(in[x],in[b],1,n,1);
        b=par[x];
    }
    if(dep[a]>dep[b]) swap(a, b);
    ans+=qsol(in[a]+1,in[b],1,n,1); 
    return ans;
}
 
string s;
int main(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    ll i,j,k,l,m,a,b,c,d;
    cin>>n>>m;
 
    for(i=1;i<n;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    dfs1(1);
    top[1]=1;
    dfs2(1);
 
    while(m--){
        cin>>s>>a>>b;
        if(s[0]=='P'){
            ppl(a,b,1);
        }
        else{
            cout<<psol(a,b)<<'\n';
        }
    }
}