2014年9月14日 星期日

2014/9/14 codevs 1036 商务旅行

/*
    LCA
*/
// http://codevs.cn/problem/1036/
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int N, M;

bool visit[40000];
int in[40000]; int out[40000];

vector<int> v[40000];
int clk = 0;

int fa[40000][16]; int dis[40000][16];

void DFS(int O)
{
    visit[O] = true;
    in[O] = ++clk;

    for(int vi = 0, vn = v[O].size(); vi < vn; vi++)
    {
        int to  = v[O][vi];

        if( !visit[to] )
        {
            DFS(to);
            fa[to][0] = O;
            dis[to][0] = 1;
        }
    }

    out[O] = ++clk;
}

bool is_anc(int x, int y)
{
    return in[x] <= in[y] && out[y] <= out[x];
}

int A[1000000]; int Ans = 0;

int main()
{
    scanf("%d", &N);

    for(int Ni = 1; Ni < N; Ni++)
    {
        int a, b;
        scanf("%d %d", &a, &b);

        v[a].push_back(b);
        v[b].push_back(a);
    }

    scanf("%d", &M);

    for(int Mi = 0; Mi < M; Mi++)
        scanf("%d", &A[Mi]);

    fill(visit, visit+40000, false);
    DFS(1);

    fa[1][0] = 1;

    for(int i = 1; i <= 15; i++)
        for(int Ni = 1; Ni <= N; Ni++)
        {
            int FA = fa[Ni][i-1];
            fa[Ni][i] = fa[FA][i-1];
            dis[Ni][i] = dis[Ni][i-1] + dis[FA][i-1];
        }

    for(int Mi = 1; Mi < M; Mi++)
    {
        int x = A[Mi-1], y = A[Mi];
        int _x, _y;

        _x = x; _y = y;

        for(int i = 15; i >= 0; i--)
            if( !is_anc( fa[_x][i], _y) )
            {
                Ans += dis[_x][i];
                _x = fa[_x][i];
            }

        if( !is_anc( _x, _y) ) Ans += dis[_x][0];

        _x = x; _y = y;

        for(int i = 15; i >= 0; i--)
            if( !is_anc( fa[_y][i], _x) )
            {
                Ans += dis[_y][i];
                _y = fa[_y][i];
            }

        if( !is_anc( _y, _x) ) Ans += dis[_y][0];
    }

    printf("%d\n", Ans);
}

沒有留言:

張貼留言