爬樹 題解

爬樹（mako）

題目概述

給定一顆樹，有兩種轉(zhuǎn)移方法，1.從子節(jié)點到父節(jié)點并消耗權值，2.從一個節(jié)點轉(zhuǎn)移到同深度的另一個節(jié)點\((要求兩個節(jié)點間的距離<=2*d)\)然后消耗c權值，求每個節(jié)點到根的最短距離

思考過程

首先我們要由特殊到一般

1. 先考慮一條鏈的情況，直接統(tǒng)計一個點逐步向下轉(zhuǎn)移到最后的答案就行
   然后考慮d=0的情況，也只需要逐步統(tǒng)計就行了
   以上為20分答案

2. 考慮菊花圖的情況

   在 \(n<=1e3\) 的情況下，菊花圖只需要讓同層兩節(jié)點之間建立邊并且邊權為c，然后跑一遍最短路就行
   在 \(n<=2*1e5\) 的情況下，我們發(fā)現(xiàn)如果建立邊，會導致\(n^2\)使空間內(nèi)存都爆掉，所以考慮優(yōu)化。

   通過對一個點的分析，一種就是由直接轉(zhuǎn)移而來，還有一種就是通過同層轉(zhuǎn)移而來，而我們貪心而想，如果都是同層轉(zhuǎn)移，那么要做到使同層的點的權值是最小的，這樣可以做到最小的答案，之后去做比較選擇，而式子為以下：

   \[dis[v] = min(dis[u]+val[v],dis[MINU]+val[MINV]+c) \]

3. 通過由特殊到一般，我們思考出了解決方法，接下來考慮實現(xiàn)

實現(xiàn)

1. 實現(xiàn)的難點在于，我們需要去維護一個點，在同深度所對應的每個不超過d距離的最小值，如果直接暴力枚舉，是至少為\(O(n^2)\)的，所以我們考慮怎么優(yōu)化

2. 通過考慮樹的特殊性質(zhì)，在同層的節(jié)點，進入順序與離最開始的點的距離是成單調(diào)遞增的，所以我們只需要去維護一個vector，使用雙指針（滑動窗口(限制大小為d)）去尋找一個點所有對應的點與其最小值，時間是\(O(n)\)

3. 實現(xiàn)代碼如下

   #include <bits/stdc++.h>
   #define N 1000006
   using namespace std;
   #define int long long
   const int inf = 1e18;
   
   int a[N], depp[N], fa[N][21],
       dis[N];  // a數(shù)組存儲每個節(jié)點的e_x；dep數(shù)組存儲節(jié)點深度；fa數(shù)組用于LCA的倍增表；dis數(shù)組存儲每個節(jié)點到地面的最小體力值
   int n, d, C;
   vector<int> G[N], D[N];  // D[dep]存儲所有深度為dep的節(jié)點
   
   // 深度優(yōu)先搜索，用于初始化每個節(jié)點的深度，并將同深度的節(jié)點存入D數(shù)組
   void dfs(int u) {
       D[depp[u]].push_back(u);  // 將當前節(jié)點u按深度存入對應的D數(shù)組中
       for (int v : G[u]) {      // 遍歷u的鄰接節(jié)點
           if (v == fa[u][0])    
               continue;
           fa[v][0] = u;           // 記錄v的直接父節(jié)點
           depp[v] = depp[u] + 1;  // 計算v的深度
           dfs(v);                 // 遞歸處理
       }
   }
   
   // 倍增法求最近公共祖先
   int lca(int x, int y) {
       if (x == y)  // 如果x和y是同一個節(jié)點，直接返回
           return x;
       for (int i = 20; ~i; --i) {      // 從大到小枚舉倍增的步數(shù)
           if (fa[x][i] != fa[y][i]) {  // 如果x和y的2^i級祖先不同
               x = fa[x][i];            
               y = fa[y][i];            
           }
       }
       return fa[x][0];  // 最后x和y的直接父節(jié)點就是LCA
   }
   
   // 計算x到lca(x,y)的距離（即x在LCA到x路徑上的邊數(shù)）
   int find(int x, int y) { return depp[x] - depp[lca(x, y)]; }
   
   signed main() {
       freopen("mako.in", "r", stdin);
       freopen("mako.out", "w", stdout);
       ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
   
       cin >> n >> d >> C;
       for (int i = 2; i <= n; ++i) cin >> a[i];  // 讀取每個節(jié)點（除1號根節(jié)點）的e_x
       for (int x, y, i = 1; i < n; ++i) {
           cin >> x >> y;
           G[x].push_back(y), G[y].push_back(x);
       }
   
       fa[1][0] = 1;  // 根節(jié)點1的直接父節(jié)點是自己
       dfs(1);        // 從根節(jié)點1開始DFS，初始化深度和D數(shù)組
   
       // 預處理倍增表，用于快速查詢祖先
       for (int i = 1; i < 21; ++i) {
           for (int j = 1; j <= n; ++j) fa[j][i] = fa[fa[j][i - 1]][i - 1];
       }
   
       dis[0] = inf;                   // 深度為0無意義，初始化為無窮大
       for (int i = 1; i <= n; ++i) {  // 按深度從小到大處理每個節(jié)點
           for (int j : D[i]) {        // 先計算從父節(jié)點下來的體力消耗（第一種移動方式）
               dis[j] = dis[fa[j][0]] + a[j];
           }
           // 處理同深度內(nèi)的移動（第二種移動方式），用滑動窗口找同深度內(nèi)距離不超過d的區(qū)間里的最小體力值
           for (int l = 0, r = -1; l < D[i].size(); l = r + 1) {
               // 擴展右邊界，找到當前左端點l對應的最大右區(qū)間r，使得區(qū)間內(nèi)節(jié)點與l的距離不超過d
               while (r + 1 < D[i].size() && find(D[i][l], D[i][r + 1]) <= d) ++r;
               int x = 0;
               // 在[l, r]區(qū)間內(nèi)找到體力值最小的節(jié)點x
               for (int j = l; j <= r; ++j) {
                   if (dis[D[i][j]] < dis[x])
                       x = D[i][j];
               }
               // 用x的體力值 + C 更新區(qū)間內(nèi)所有節(jié)點的最小體力值
               for (int j = l; j <= r; ++j) {
                   dis[D[i][j]] = min(dis[D[i][j]], dis[x] + C);
               }
           }
       }
   
       for (int i = 1; i <= n; ++i) cout << dis[i] << " ";
       return 0;
   }