首先, 文对于 线段 \([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;
}
标签:2024.2,21,int,LCA,mid,++,edge,ans,游记
From: https://www.cnblogs.com/liuyichen0401/p/18026390