LCA Codeforces 100685G Gadget Hackwrench-白红宇

LCA Codeforces 100685G Gadget Hackwrench

阅读量：6080 次

发布时间：2019-06-20

本文共 1568 字，大约阅读时间需要 5 分钟。

题意：一棵有向的树，问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 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef 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
                      
                       > 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