P10289 [GESP样题 八级] 小杨的旅游

Description

给定一棵

     n 
    
   
  
    n 
   
  
n 个点的树，每条边权值均为  
 
  
   
   
     1 
    
   
  
    1 
   
  
1，树上有  
 
  
   
   
     k 
    
   
  
    k 
   
  
k 个关键点，关键点们在  
 
  
   
   
     0 
    
   
  
    0 
   
  
0 的时间内相互可达， 
 
  
   
   
     q 
    
   
  
    q 
   
  
q 次询问，求  
 
  
   
   
     s 
    
   
     → 
    
   
     t 
    
   
  
    s\to t 
   
  
s→t 的最短路。

Analysis

考虑暴力建图，则图上共有

     ( 
    
   
     n 
    
   
     − 
    
   
     1 
    
   
     + 
    
    
     
     
       n 
      
     
       ( 
      
     
       n 
      
     
       − 
      
     
       1 
      
     
       ) 
      
     
    
      2 
     
    
   
     ) 
    
   
  
    (n-1+\frac{n(n-1)}{2}) 
   
  
(n−1+2n(n−1)​)条边，在  
 
  
   
   
     n 
    
   
     , 
    
   
     k 
    
   
  
    n,k 
   
  
n,k 均为最大的情况下，图上共有大约  
 
  
   
   
     2 
    
   
     × 
    
   
     1 
    
    
    
      0 
     
    
      10 
     
    
   
  
    2 \times 10^{10} 
   
  
2×1010 条边，铁定 

MLE

。

我们注意到，从

     s 
    
   
  
    s 
   
  
s 到  
 
  
   
   
     t 
    
   
  
    t 
   
  
t 只有两种情况：

• 老老实实从树上走；
• 从 s s s 走到一个关键点 k 1 k_1 k1​，穿越到另一个关键点 k 2 k_2 k2​，再走到 t t t。

第一种情况就是常规树上两点最短路。
第二种情况，根据贪心思想，选取的

      k 
     
    
      1 
     
    
   
     , 
    
    
    
      k 
     
    
      2 
     
    
   
  
    k_1,k_2 
   
  
k1​,k2​ 一定是距离  
 
  
   
   
     s 
    
   
     , 
    
   
     t 
    
   
  
    s,t 
   
  
s,t 最近的两个。所以我们初始时一次 

bfs

求出每个点

     i 
    
   
  
    i 
   
  
i 到传送门的距离  
 
  
   
   
     d 
    
   
     s 
    
    
    
      t 
     
    
      i 
     
    
   
  
    dst_i 
   
  
dsti​，最终答案即为  
 
  
   
   
     d 
    
   
     s 
    
    
    
      t 
     
    
      s 
     
    
   
     + 
    
   
     d 
    
   
     s 
    
    
    
      t 
     
    
      t 
     
    
   
  
    dst_s+dst_t 
   
  
dsts​+dstt​。

Code

// Problem: P10289 [GESP样题 八级] 小杨的旅游// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P10289// Memory Limit: 512 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)#include<iostream>#include<queue>#include<cmath>usingnamespace std;using Graph = vector<vector<int>>;constint INF =1e9;structLCA{int n, k;
    vector<int> dep;
    vector<vector<int>> f;
    Graph G;LCA(){}LCA(const Graph &tree):G(tree){
        n = G.size();
        k =(int)log2(n)+1;
        
        dep.assign(n,0);
        f.assign(n,vector<int>(k,-1));dfs(0,0);}voiddfs(int u,int fa){
        dep[u]= dep[fa]+1;
        f[u][0]= fa;for(int i =1; i < k; i++) f[u][i]= f[f[u][i -1]][i -1];for(auto v: G[u]){if(v == fa)continue;dfs(v, u);}}intlca(int x,int y){if(dep[x]< dep[y])swap(x, y);for(int i = k -1; i >=0; i--)if(dep[f[x][i]]>= dep[y]) x = f[x][i];if(x == y)return x;for(int i = k -1; i >=0; i --)if(f[x][i]!= f[y][i]){
                x = f[x][i];
                y = f[y][i];}return f[x][0];}intdist(int x,int y){return dep[x]+ dep[y]-2* dep[lca(x, y)];}};signedmain(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);int n, k, q;
    cin >> n >> k >> q;
    
    Graph G(n);for(int i =0, u, v; i < n -1; i++){
        cin >> u >> v;
        u--, v--;
        G[u].push_back(v);
        G[v].push_back(u);}
    
    LCA tree(G);
    queue<int> que;
    vector<int>dis(n, INF);for(int i =0, x; i < k; i++){
        cin >> x;
        x--;
        que.push(x);
        dis[x]=0;}while(que.size()){int u = que.front();
        que.pop();for(auto v: G[u])if(dis[v]== INF){
                dis[v]= dis[u]+1;
                que.push(v);}}auto dist =[&](int x,int y){returnmin(tree.dist(x, y), dis[x]+ dis[y]);};for(int i =0, u, v; i < q; i++){
        cin >> u >> v;
        u--, v--;
        cout <<dist(u, v)<< endl;}return0;}