题目大意

给定一棵树，求以题目给出的路径走需要的最小代价

思路

就是一个LCA，就不解释了
这题在写的时候忘了C++数组从0开始，开少了一位

#include 
#include 
#define max 15
#define M 100000
int f[M][max+1],head[M],g[M][max+1],deep[M];
bool vis[M];
int ans,n;
struct arr
{
    int x,w,last;
};
arr edge[M];
int dfs(int x,int dep)
{
    vis[x]=true;
    deep[x]=dep;
    int p=head[x];
    while (p!=-1)
    {
        if (vis[edge[p].x]==false)
        {
            g[edge[p].x][0]=edge[p].w;
            f[edge[p].x][0]=x;
            dfs(edge[p].x,dep+1);
        }
        p=edge[p].last;
    }
    return 0;
}
int make()
{
    for (int j=1;j<=max;j++)
        for (int i=1;i<=n;i++)
            if (f[i][j-1]!=-1)
            {
                f[i][j]=f[f[i][j-1]][j-1];
                g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1];
            }
    return 0;
}
int find(int x,int y)
{
    if (deep[x]=1;i--)
    {
        if (deep[f[x][i]]>deep[y])
        {
            ans+=g[x][i];
            x=f[x][i];
        }
    }
    while (deep[x]>deep[y])
    {
        ans+=g[x][0];
        x=f[x][0];
    }
    if (x==y) return 0;
    for (int i=max;i>=1;i--)
        if (f[x][i]!=f[y][i])
        {
            ans=ans+g[x][i]+g[y][i];
            x=f[x][i];
            y=f[y][i];
        }
    while (x!=y)
    {
        ans+=g[x][0]+g[y][0];
        x=f[x][0];
        y=f[y][0];
    }
    return 0;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        head[i]=-1;
    int l=0;
    for (int i=1;i<=n-1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        l++;
        edge[l].x=y;
        edge[l].w=1;
        edge[l].last=head[x];
        head[x]=l;
        l++;
        edge[l].x=x;
        edge[l].w=1;
        edge[l].last=head[y];
        head[y]=l;
    }
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    memset(vis,0,sizeof(vis));
    for (int j=0;j<=max;j++)
        for (int i=1;i<=n;i++)
            f[i][j]=-1;

    dfs(1,1);   

    make();
    int m,x,sum=0;
    scanf("%d%d",&m,&x);
    for (int i=1;i<=m-1;i++)
    {
        ans=0;
        int y;
        scanf("%d",&y);

        find(x,y);
        sum+=ans;
        x=y;
    }
    printf("%d\n",sum);
}

#include 
#define maxn 60001
struct edge
{
    int to, next;
}e[maxn];
int ls[maxn], f[maxn][21], dep[maxn];
__attribute__((optimize("-O2")))
inline int dfs(int fa, int now)
{
    f[now][0] = fa;
    dep[now] = dep[fa] + 1;
    for (int i = ls[now]; i; i = e[i].next)
        if (!dep[e[i].to]) dfs(now, e[i].to);
}
inline __attribute__((optimize("-O2")))
int LCA(int l, int r)
{
    if (dep[l] < dep[r])
        {l ^= r; r ^= l; l ^= r;}
    for (int i = 20; i >= 0; i--)
        if (dep[r] <= dep[f[l][i]])
            l = f[l][i];
    if (l == r) return l;
    for (int i = 20; i >= 0; i--)
        if (f[l][i] != f[r][i])
        {
            l = f[l][i];
            r = f[r][i];
        }
    return f[l][0];
}
int main()
{
    int n, l = 0;
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        e[++l] = (edge) {y, ls[x]};
        ls[x] = l;
        e[++l] = (edge) {x, ls[y]};
        ls[y] = l;
    }

    dfs(0, 1);


    for (int j = 1; j <= 20; j++)
        for (int i = 1; i <= n; i++)
            f[i][j] = f[f[i][j - 1]][j - 1];
    int m, now, last, ans = 0;
    scanf("%d%d", &m, &last);
    for (int i = 2; i <= m; i++)
    {
        scanf("%d", &now);
        ans += dep[last] + dep[now] - dep[LCA(last, now)] * 2;
        last = now;
    }
    printf("%d\n", ans);
}