CODE[VS] 1036 商务旅行（LCA + BFS）

在输出文件中输出该商人旅行的最短时间。

样例输入

5

1 2

1 5

3 5

4 5

4

1

3

2

5

样例输出

7

#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <algorithm>#include <vector>#include <queue>#include <stack>#include <set>#include <map>using namespace std;const int MAXN = 30000 + 10;int rmq[2*MAXN];//建立RMQ的数组//***************************//ST算法，里面含有初始化init(n)和query(s,t)函数//点的编号从1开始，1-n.返回最小值的下标//***************************struct ST{int mm[2*MAXN];//mm[i]表示i的最高位，，mm[1]=0,mm[2]=1,mm[3]=1,mm[4]=2int dp[MAXN*2][20];void init(int n){mm[0]=-1;for(int i=1;i<=n;i++){mm[i]=((i&(i-1))==0?mm[i-1]+1:mm[i-1]);dp[i][0]=i;}for(int j=1;j<=mm[n];j++)for(int i=1;i+(1<<j)-1<=n;i++)dp[i][j]=rmq[dp[i][j-1]]<rmq[dp[i+(1<<(j-1))][j-1]]?dp[i][j-1]:dp[i+(1<<(j-1))][j-1];}int query(int a,int b)//查询a到b间最小值的下标{if(a>b)swap(a,b);int k=mm[b-a+1];return rmq[dp[a][k]]<rmq[dp[b-(1<<k)+1][k]]?dp[a][k]:dp[b-(1<<k)+1][k];}};//边的结构体定义struct Node{int to,next;};/* ******************************************LCA转化为RMQ的问题MAXN为最大结点数。ST的数组 和 F，edge要设置为2*MAXNF是欧拉序列，rmq是深度序列，P是某点在F中第一次出现的下标*********************************************/struct LCA2RMQ{int n;//结点个数Node edge[2*MAXN];//树的边,因为是建无向边，所以是两倍int tol;//边的计数int head[MAXN];//头结点bool vis[MAXN];//访问标记int F[2*MAXN];//F是欧拉序列，就是DFS遍历的顺序int P[MAXN];//某点在F中第一次出现的位置int cnt;ST st;void init(int n)//n为所以点的总个数，可以从0开始，也可以从1开始{this->n=n;tol=0;memset(head,-1,sizeof(head));}void addedge(int a,int b)//加边{edge[tol].to=b;edge[tol].next=head[a];head[a]=tol++;edge[tol].to=a;edge[tol].next=head[b];head[b]=tol++;}int query(int a,int b)//传入两个节点，返回他们的LCA编号{return F[st.query(P[a],P[b])];}void dfs(int a,int lev){vis[a]=true;++cnt;//先加，保证F序列和rmq序列从1开始F[cnt]=a;//欧拉序列，编号从1开始，共2*n-1个元素rmq[cnt]=lev;//rmq数组是深度序列P[a]=cnt;for(int i=head[a];i!=-1;i=edge[i].next){int v=edge[i].to;if(vis[v])continue;dfs(v,lev+1);++cnt;F[cnt]=a;rmq[cnt]=lev;}}void solve(int root){memset(vis,false,sizeof(vis));cnt=0;dfs(root,0);st.init(2*n-1);}}lca;int dis[MAXN];vector<int>G[MAXN];int P[MAXN];void bfs(){queue<int>Q;Q.push(1);memset(dis, -1, sizeof(dis));dis[1] = 0;while(!Q.empty()){int u = Q.front();Q.pop();int sz = G[u].size();for(int i=0;i<sz;i++){int v = G[u][i];//cout << v << endl;if(dis[v] == -1){dis[v] = dis[u] + 1;Q.push(v);}}}}int main(){int N;while(scanf("%d", &N)!=EOF){int u, v;lca.init(N);for(int i=0;i<=N;i++) G[i].clear();for(int i=1;i<N;i++){scanf("%d%d", &u, &v);lca.addedge(u, v);G[u].push_back(v);G[v].push_back(u);}bfs();lca.solve(1);int ans = 0;int M;scanf("%d", &M);for(int i=1;i<=M;i++)scanf("%d", &P[i]);for(int i=1;i<M;i++){int fa = lca.query(P[i], P[i+1]);//cout << P[i] << ' ' << P[i+1] << ' ' << fa << endl;ans += (dis[P[i]] + dis[P[i+1]] – 2 * dis[fa]);}printf("%d\n", ans);}return 0;}

有事者，事竟成;破釜沉舟，百二秦关终归楚;苦心人，