LCA Codeforces 100685G Gadget Hackwrench

题目传送门

题意：一棵有向的树，问u到v是否可达

分析：假设是无向树，DFS时正向的权值+1，反向的权值-1，然后找到LCA后判断dep数组和d数组就可以了

/************************************************

* Author        :Running_Time

* Created Time  :2015/10/5 星期一 10:28:49

* File Name     :G_2.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int D = 20;

const int MOD = 1e9 + 7;

const double EPS = 1e-8;

struct Edge {

    int v, d, nex;

}edge[N<<1];

int rt[D][N];

int dep[N], d[N];

int head[N], e;

void init(void) {

    memset (head, -1, sizeof (head));

    e = 0;

}

void add_edge(int u, int v, int dir) {

    edge[e] = (Edge) {v, dir, head[u]};

    head[u] = e++;

}

void DFS(int u, int fa, int dis)  {

    dep[u] = dep[fa] + 1;

    d[u] = dis;

    for (int i=head[u]; ~i; i=edge[i].nex)  {

        int v = edge[i].v;

        if (v == fa)    continue;

        rt[0][v] = u;

        DFS (v, u, dis + edge[i].d);

    }

}

int LCA(int u, int v)  {

    if (dep[u] < dep[v])    {

        swap (u, v);

    }

    for (int i=0; i<D; ++i)  {

        if ((dep[u] - dep[v]) >> i & 1)    {

            u = rt[i][u];

        }

    }

    if (u == v) return u;

    for (int i=D-1; i>=0; --i)  {

        if (rt[i][u] != rt[i][v])   {

            u = rt[i][u];

            v = rt[i][v];

        }

    }

    return rt[0][v];

}

int main(void)    {

    int n;

    while (scanf ("%d", &n) == 1)   {

        init ();

        for (int u, v, i=1; i<n; ++i) {

            scanf ("%d%d", &u, &v);

            add_edge (u, v, 1);

            add_edge (v, u, -1);

        }

        DFS (1, 0, 0);

        for (int i=1; i<D; ++i) {

            for (int j=1; j<=n; ++j)    {

                rt[i][j] = rt[i-1][rt[i-1][j]];

            }

        }

        int m;  scanf ("%d", &m);

        while (m--) {

            int u, v;   scanf ("%d%d", &u, &v);

            int f = LCA (u, v);

            if (dep[u] - dep[f] != d[f] - d[u]) puts ("No");

            else if (dep[v] - dep[f] != d[v] - d[f])    puts ("No");

            else    puts ("Yes");

        }

    }

    return 0;

}