二分+树剖
开始题目理解错了,这里的最短时间指的是所有路径的最大值。所以题目要求的就是让所有路径的最大值最小,显然可以二分。
二分最大值 \(x\),那么假如一条路径长度为 \(d\) 并且 \(d>x\),显然需要修改,即一定要删去路径上的一条边 \((u,v)\),满足 \(d-w(u,v)\le x\),即 \(w(u,v)\ge d-x\)。开始的时候想的做法是,把每条路径满足这个条件的边标记+1,最后看是否有这样的边满足标记等于需要修改的路径数,可我们并没有这样一个数据结构能够快速找到满足这种条件的边。
考虑另一个角度,可以发现我们要修改的边一定是所有需要修改的路径的交集,所以我们完全可以找到这个交集,再判断交集内的边是否有满足 \(w\ge\max(d)-x\)。这个做法只需要把需要修改的路径上的边+1,树剖即可。这里的角度是把修改的边集找出来,最后再判断边集中是否有边满足条件。
先二分,再树剖标记,这样的复杂度为 \(O((m\log n+n)\log V)\),可以通过。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back
typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 10;
int n, m, cnt;
int dis[N], h[N];
std::array<int, 3> G[N];
bool cmp(std::array<int, 3> a, std::array<int, 3> b) {
return a[2] > b[2];
}
struct node {
int to, nxt, w;
} e[N << 1];
void add(int u, int v, int w) {
e[++cnt].to = v, e[cnt].nxt = h[u], e[cnt].w = w, h[u] = cnt;
}
int num;
int sz[N], dep[N], id[N], son[N], fa[N], top[N], val[N];
void dfs1(int u, int f) {
sz[u] = 1;
dep[u] = dep[f] + 1;
fa[u] = f;
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to, w = e[i].w;
if(v == f) continue;
dis[v] = dis[u] + w;
dfs1(v, u);
val[v] = w;
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int topf) {
top[u] = topf;
id[u] = ++num;
if(!son[u]) return;
dfs2(son[u], topf);
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
}
int lca(int u, int v) {
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]]) std::swap(u, v);
u = fa[top[u]];
}
if(dep[u] > dep[v]) std::swap(u, v);
return u;
}
struct seg {
int v, lzy;
} t[N << 2];
void pushup(int u) {t[u].v = t[u << 1].v + t[u << 1 | 1].v;}
void pd(int u, int l, int r) {
if(!t[u].lzy) return;
int mid = (l + r) >> 1;
t[u << 1].v += (mid - l + 1) * t[u].lzy; t[u << 1 | 1].v += (r - mid) * t[u].lzy;
t[u << 1].lzy += t[u].lzy, t[u << 1 | 1].lzy += t[u].lzy;
t[u].lzy = 0;
}
void build(int u, int l, int r) {
t[u].v = t[u].lzy = 0;
if(l == r) return;
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
int query(int u, int l, int r, int x) {
if(l == r) return t[u].v;
int mid = (l + r) >> 1; pd(u, l, r);
if(x <= mid) return query(u << 1, l, mid, x);
return query(u << 1 | 1, mid + 1, r, x);
}
void update(int u, int l, int r, int L, int R, int x) {
if(L <= l && r <= R) {
t[u].v += (r - l + 1) * x;
t[u].lzy += x;
return;
}
int mid = (l + r) >> 1; pd(u, l, r);
if(L <= mid) update(u << 1, l, mid, L, R, x);
if(R > mid) update(u << 1 | 1, mid + 1, r, L, R, x);
pushup(u);
}
void mdf(int u, int v) {
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]]) std::swap(u, v);
update(1, 1, n, id[top[u]], id[u], 1);
u = fa[top[u]];
}
if(dep[u] > dep[v]) std::swap(u, v);
update(1, 1, n, id[u] + 1, id[v], 1);
}
bool check(int x) {
build(1, 1, n);
int cnt = 0, mx = 0, nd = 0;
for(int i = 1; i <= m; i++) {
if(G[i][2] <= x) break;
mdf(G[i][0], G[i][1]); cnt++;
}
if(!cnt) return 1;
for(int i = 2; i <= n; i++) {
if(query(1, 1, n, id[i]) == cnt) mx = std::max(mx, val[i]);
}
return mx >= G[1][2] - x;
}
void Solve() {
std::cin >> n >> m;
for(int i = 1; i < n; i++) {
int u, v, w;
std::cin >> u >> v >> w;
add(u, v, w), add(v, u, w);
}
dfs1(1, 0), dfs2(1, 1);
for(int i = 1; i <= m; i++) {
std::cin >> G[i][0] >> G[i][1];
int rt = lca(G[i][0], G[i][1]);
G[i][2] = dis[G[i][0]] + dis[G[i][1]] - 2 * dis[rt];
}
std::sort(G + 1, G + m + 1, cmp);
int l = 0, r = 300000000, ans = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}
标签:std,运输,NOIP2015,int,top,路径,P2680,son,dep
From: https://www.cnblogs.com/FireRaku/p/18118889