2024.2.21游记

Orz AKer / 2024-02-22 / 原文

首先, 文对于线段 $[A, B]$, $[C, D]$ 什么时候相交。 $B$ 为 $A$ 的祖先, $D$ 为 $C$ 的祖先

相交有一种情况, 在 $[A, B]$ 上有一个分叉, 连接 $C$, 然后分叉上面为 $D$, 这是候, 就会发现 $B$ 是 $C$ 的祖先, $D$ 是 $A$ 的祖先

代码形式

LCA(B, C) == B && LCA(D, A) == D

NOIP2015 运输计划

可以二分一个答案 $x$, 显然, $x$ 具有单调性。 $x$ 越多越合法

对于一个长度 $>$ $x$ 的答案, 要求出一个这些线段都能到达的边, 求边的最大值, 求完之后判读合法

时间复杂度 $O(N log V)$

对于某一些题, 时限为 $1s$, 要用一些卡常技巧

二分上界为 $\sum w_i$
vector 建图转成链式前向星
每一次二分都跑一遍 DFS 常数太大, 先跑一遍记录 DFS 序, 每一次从后往前做转移
用一个数组存下线段段点的 $LCA$, 不用每一次都重新算

#include<bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

int l, r, mid, dep[N], f[19][N], dist[N], a[N], b[N], u, v, w, k, len, Max, n, m, ans[N], lca[N], ok, head[N], tot;

struct Node{
  int v, w;
};

struct Edge{
  int v, w, net;
}e[N * 2];

vector<int>edge;

void dfs(int x, int fa){
  dep[x] = dep[fa] + 1;
  edge.push_back(x);
  f[0][x] = fa;
  for(int i = 1; i <= 18; ++i){
    f[i][x] = f[i - 1][f[i - 1][x]];
  }
  for(int i = head[x]; i; i = e[i].net){
    auto v = e[i].v, w = e[i].w;
    if(v != fa){
      dist[v] = dist[x] + w;
      dfs(v, x);
    }
  }
}

int LCA(int x, int y){
  if(dep[x] < dep[y]){
    swap(x, y);
  }
  k = dep[x] - dep[y];
  for(int i = 18; ~i; i--){
    if(k & (1 << i)){
      x = f[i][x];
    }
  }
  if(x == y){
    return x;
  }
  for(int i = 18; ~i; i--){
    if(f[i][x] != f[i][y]){
      x = f[i][x], y = f[i][y];
    }
  }
  return f[0][x];
}

bool C(int t){
  for(int i = 1; i <= n; ++i){
    ans[i] = 0;
  }
  len = 0;
  Max = -1;
  for(int i = 1; i <= m; ++i){
    if(dist[a[i]] + dist[b[i]] - 2 * dist[lca[i]] > t){
      len++;
      ans[a[i]]++, ans[b[i]]++, ans[lca[i]] -= 2;
    }
  }
  for(int i = edge.size() - 1; ~i; i--){
    int x = edge[i];
    for(int i = head[x]; i; i = e[i].net){
      auto v = e[i].v, w = e[i].w;
      if(f[0][x] != v){
        if(ans[v] == len){
          Max = max(Max, w);
        }
        ans[x] += ans[v];
      }
    }
  }
  if(Max == -1){
    return 0;
  }
  for(int i = 1; i <= m; ++i){
    if(dist[a[i]] + dist[b[i]] - 2 * dist[lca[i]] - Max > t){
      return 0;
    }
  }
  return 1;
}

void add_edge(int u, int v, int w){
  e[++tot] = {v, w, head[u]}, head[u] = tot;
}

signed main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for(int i = 1; i < n; ++i){
    cin >> u >> v >> w;
    add_edge(u, v, w);
    add_edge(v, u, w);
    ok += w;
  }
  dfs(1, 0);
  for(int i = 1; i <= m; ++i){
    cin >> a[i] >> b[i];
    lca[i] = LCA(a[i], b[i]);
  }
  l = 0, r = ok;
  while(l < r){
    mid = (l + r) >> 1;
    if(C(mid)){
      r = mid;
    }
    else{
      l = mid + 1;
    }
  }
  cout << l;
  return 0;
}