광덕산 등산 (JUNGOL 8671)

https://jungol.co.kr/problem/8671

---

아이디어

경로는 정해져있습니다. 같은 간선을 왔다갔다 하는것은 A+B>=0이므로 이득일 수 없습니다. 그러므로 경로는 정해집니다. 또한 a에서 b로 가는 경로는 LCA를 통해 a->lca와 b->lca의 합성으로 구할 수 있습니다. 이제 우리가 구해야하는것은 a->lca에서의 결과적인 높이차, 그 과정에서의 가장 높이 올라가는 값, lca->b에서의 결과적인 높이차, 그 과정에서의 가장 높이 올라가는 값입니다. 사실 높이가 아니라 체력이긴 한데 그냥 높이로 부릅시다.

 

이는 LCA에서의 희소배열을 이용해주면 됩니다. UpHeight[i][a]는 노드 i에서 2^a만큼 올라간 조상까지 올라갈 때 높이차입니다. 반대로 DownHeight[i][a]는 노드 i에서 2^a만큼 조상부터 노드 i까지 내려올 때 높이차입니다. UpMaxHeight[i][a]는 노드 i에서 2^a만큼 올라간 조상까지 올라갈 때 그 경로에서 가장 높이 올라가는 값입니다. DownMaxHeight[i][a]는 노드 i에서 2^a만큼 올라간 조상부터 i까지 내려올 때 그 경로에서 가장 높이 올라가는 값입니다. 이 배열들을 DFS 한번으로 채워줍니다.

 

그러면 a,b,lca가 주어졌을 때 a->lca에서의 정보, lca->a에서의 정보를 구할 수 있습니다. 이를 바탕으로 정답값을 구해주면 됩니다.

---

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

ll A,B;
int Height[202020]={0};
int par[202020][22]={0},dpt[202020]={0};
ll UpHeight[202020][22]={0},UpMaxHeight[202020][22]={0};
ll DownHeight[202020][22]={0},DownMaxHeight[202020][22]={0};
vector <int> Graph[202020];

void DFS(int node,int before)
{
    par[node][0]=before;
    dpt[node]=dpt[before]+1;
    UpHeight[node][0]=(Height[node]>Height[before]?B*(Height[node]-Height[before]):A*(Height[before]-Height[node]));
    UpMaxHeight[node][0]=max((ll)(0),UpHeight[node][0]);
    DownHeight[node][0]=(Height[node]>Height[before]?A*(Height[node]-Height[before]):B*(Height[before]-Height[node]));
    DownMaxHeight[node][0]=max((ll)(0),DownHeight[node][0]);
    for (int i=1;i<=20;i++)
    {
        par[node][i]=par[par[node][i-1]][i-1];
        UpHeight[node][i]=UpHeight[node][i-1]+UpHeight[par[node][i-1]][i-1];
        UpMaxHeight[node][i]=max(UpMaxHeight[node][i-1],UpHeight[node][i-1]+UpMaxHeight[par[node][i-1]][i-1]);
        DownHeight[node][i]=DownHeight[node][i-1]+DownHeight[par[node][i-1]][i-1];
        DownMaxHeight[node][i]=max(DownMaxHeight[par[node][i-1]][i-1],DownHeight[par[node][i-1]][i-1]+DownMaxHeight[node][i-1]);
    }

    for (ll next:Graph[node])
    {
        if (next==before) continue;
        DFS(next,node);
    }
}
int LCA(int a,int b)
{
    int i;
    if (dpt[a]<dpt[b]) swap(a,b);
    for (i=20;i>=0;i--)
    {
        if (dpt[par[a][i]]>=dpt[b]) 
            a=par[a][i];
    }
    if (a==b) return a;
    for (i=20;i>=0;i--)
    {
        if (par[a][i]!=par[b][i])
            a=par[a][i],b=par[b][i];
    }
    return par[a][0];
}

void Move(int a,int b,array <ll,4> &res) //b가 a의 조상
{
    //{UpHeight,UpMaxHeight,DownHeight,DownMaxHeight}
    int i;
    for (i=20;i>=0;i--)
    {
        if (dpt[par[a][i]]>=dpt[b])
        {
            res[1]=max(res[1],res[0]+UpMaxHeight[a][i]);
            res[0]+=UpHeight[a][i];
            res[3]=max(DownMaxHeight[a][i],DownHeight[a][i]+res[3]);
            res[2]+=DownHeight[a][i];
            a=par[a][i];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,x,y,z;

    cin>>N>>A>>B;
    for (i=1;i<=N;i++) cin>>Height[i];
    for (i=0;i<N-1;i++)
    {
        cin>>x>>y;
        Graph[x].push_back(y);
        Graph[y].push_back(x);
    }

    DFS(1,0);

    ll Q,lca,H,MaxH;
    array <ll,4> Up,Down;

    cin>>Q;
    for (i=0;i<Q;i++)
    {
        cin>>x>>y>>z;

        lca=LCA(x,y);

        Up={0,0,0,0},Down={0,0,0,0};
        Move(x,lca,Up); Move(y,lca,Down);
        H=Up[0]+Down[2],MaxH=max(Up[1],Up[0]+Down[3]);

        //cout<<Up[0]<<' '<<Up[1]<<' '<<Up[2]<<' '<<Up[3]<<"\n"<<Down[0]<<' '<<Down[1]<<' '<<Down[2]<<' '<<Down[3]<<"\n";
        //cout<<lca<<' '<<H<<' '<<MaxH<<"??\n";

        if (MaxH>z) cout<<"-1\n";
        else cout<<z-H<<"\n";
    }
}