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

#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]=2 int dp[MAXN*2][20]; void init(int n) { mm[0]=⑴; for(int i=1;i<=n;i++) { mm[i]=((i&(i⑴))==0?mm[i⑴]+1:mm[i⑴]); dp[i][0]=i; } for(int j=1;j<=mm[n];j++) for(int i=1;i+(1<<j)⑴<=n;i++) dp[i][j]=rmq[dp[i][j⑴]]<rmq[dp[i+(1<<(j⑴))][j⑴]]?dp[i][j⑴]:dp[i+(1<<(j⑴))][j⑴]; } 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*MAXN F是欧拉序列，rmq是深度序列，P是某点在F中第1次出现的下标 *********************************************/ 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中第1次出现的位置 int cnt; ST st; void init(int n)//n为所以点的总个数，可以从0开始，也能够从1开始 { this->n=n; tol=0; memset(head,⑴,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⑴个元素 rmq[cnt]=lev;//rmq数组是深度序列 P[a]=cnt; for(int i=head[a];i!=⑴;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⑴); } }lca; int dis[MAXN]; vector<int>G[MAXN]; int P[MAXN]; void bfs() { queue<int>Q; Q.push(1); memset(dis, ⑴, 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] == ⑴) { 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 ", ans); } return 0; }