wikioi1036 商务旅行挺水的lca

题意不写了。
思路：很明显找到lca然后用两个点的深度相加-lca的深度就是这一步的最近步数。
  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <stdlib.h>
  6 #include <vector>
  7 #include <queue>
  8 #define loop(s,i,n) for(i = s;i < n;i++)
  9 #define cl(a,b) memset(a,b,sizeof(a))
 10 using namespace std;
 11 const int maxn = 100005;
 12 int low[maxn],dfn[maxn],set[maxn],father[maxn],dfsclock,cut;
 13 int depth[maxn];
 14 
 15 vector<int >g[maxn];
 16 int find(int x)
 17 {
 18     if(set[x] != x)
 19     set[x] = find(set[x]);
 20 
 21     return set[x];
 22 }
 23 int merge(int x,int y)
 24 {
 25     x = find(x);
 26     y = find(y);
 27     if(y != x)
 28     {
 29         set[y] = x;
 30         return 1;
 31     }
 32     return 0;
 33 }
 34 void tarjan(int u,int pre,int deep)
 35 {
 36     int v,i,j;
 37     dfn[u] = low[u] = ++dfsclock;
 38     depth[u] = deep;
 39     loop(0,i,g[u].size())
 40     {
 41         v = g[u][i];
 42         if(!dfn[v])
 43         {
 44             tarjan(v,u,deep+1);
 45             father[v] = u;
 46             low[u] = min(low[v],low[u]);
 47             if(low[v] > dfn[u])
 48             cut++;
 49             else
 50             merge(u,v);
 51         }
 52         else if(v != pre)
 53         low[u] = min(low[u],dfn[v]);
 54     }
 55 }
 56 int lca(int u,int v)
 57 {
 58 
 59     while(u != v)
 60     {
 61         while(dfn[u] >= dfn[v] && u != v)
 62         {
 63             if(merge(u,father[u]))
 64             cut--;
 65             u = father[u];
 66         }
 67         while(dfn[v] >= dfn[u] && u != v)
 68         {
 69             if(merge(v,father[v]))
 70             cut--;
 71             v =  father[v];
 72         }
 73     }
 74     return u;
 75 }
 76 int main()
 77 {
 78     int n,m;
 79     int i,x,y;
 80     scanf("%d",&n);
 81     {
 82         int u,v;
 83         loop(0,i,n+1)
 84         {
 85             g[i].clear();
 86             set[i] = i;
 87             father[i] = 0;
 88         }
 89         loop(1,i,n)
 90         {
 91             scanf("%d %d",&u,&v);
 92             g[u].push_back(v);
 93             g[v].push_back(u);
 94 
 95         }
 96         cl(dfn,0);
 97         cl(low,0);
 98         cut = dfsclock = 0;
 99 
100         int k;
101         scanf("%d",&k);
102         tarjan(1,-1,0);
103         u = 1;
104         int ans;
105         ans = 0;
106         while(k--)
107         {
108             scanf("%d",&v);
109             int f;
110             f = lca(u,v);
111             ans += depth[u]+depth[v]-2*depth[f];
112             u = v;
113         }
114         cout<<ans<<endl;
115     }
116     return 0;
117 }
View Code
wikioi1036 商务旅行 挺水的lca

wikioi1036 商务旅行挺水的lca
