小A的最短路

题意：
有一颗n个节点的树，经过一条边消耗一点体力。有两个特殊点之间有一个观光缆车，他们之间不需要消耗体力。有Q个询问，每个询问求从x点到y点消耗体力值最少为多少？

思路：
求任意两点树上的距离应该用LCA.
由于多了个电缆，所以我们从x到y是有3种方案：
①从x直接到y，不坐电缆。
②从x到u，再从u坐电缆到v,最后从v到y。
③从x到v，再从v坐电缆到u,最后从u到y。
我们取这三种方案的最少值就可以了

注意：
lca写的丑的会被卡时间，由于u，v固定，所以可以用dfs先求出树上每一个节点到u，v的距离进行优化。

代码：

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll inf=998244353;

inline int read()
{
    int x=0, y=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
        {
            y=-y;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*y;
}

vector<int> g[300005];
int dep[300005], parent[20][300005];
int n;

void dfs(int v,int f,int d)
{
    dep[v]=d;
    parent[0][v]=f;
    for(int k=0;(1<<(k+1))<=dep[v];k++)
    {
         if(parent[k][v]<0)
         {
             parent[k+1][v]=-1;
             break;
         }
         else
         {
             parent[k+1][v]=parent[k][parent[k][v]];
         }
    }
    for(int i=0;i<g[v].size();i++)
    {
        if(g[v][i]!=f)
        {
            dfs(g[v][i],v,d+1);
        }
    }
}

int d1[300005], d2[300005];

void dfs1(int v,int f,int d)
{
    d1[v]=d;
    for(int i=0;i<g[v].size();i++)
    {
        if(g[v][i]!=f)
        {
            dfs1(g[v][i],v,d+1);
        }
    }
}

void dfs2(int v,int f,int d)
{
    d2[v]=d;
    for(int i=0;i<g[v].size();i++)
    {
        if(g[v][i]!=f)
        {
            dfs2(g[v][i],v,d+1);
        }
    }
}

void inti()
{
    memset(parent,-1,sizeof(parent));
    dfs(1,-1,0);
}

int lca(int u,int v)
{
    if(dep[u]<dep[v])
    {
        swap(u,v);
    }
    int s=(int)log2(n);
    for(int k=s;k>=0;k--)
    {
        if((dep[u]-dep[v])>=(1<<k))
        {
            u=parent[k][u];
        }
    }
    if(u==v)
    {
        return u;
    }
    for(int k=s;k>=0;k--)
    {
        if(parent[k][v]!=parent[k][u])
        {
            u=parent[k][u];
            v=parent[k][v];
        }
    }
    return parent[0][u];
}

int dis(int x, int y)
{
    return dep[x]+dep[y]-2*dep[lca(x,y)];
}

int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int u=read(), v=read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    inti();
    int u, v;
    u=read();
    v=read();
    dfs1(u,-1,0);
    dfs2(v,-1,0);
    int q=read();
    while(q--)
    {
        int x=read(), y=read();
        printf("%d\n",min(dis(x,y),min(d1[x]+d2[y],d1[y]+d2[x])));
    }
    return 0;
}