当前位置：首页 > news >正文

树上问题

news 2026/6/11 21:46:00

运输计划

比较简单的题，9.13一遍过
首先比较容易想到二分，那么如何check呢，把所有大于mid的运输计划拎出来
这些之中应该找到他们交集中最大的一条，如果将他变成虫洞可以那就ok

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i ++ )
#define repf(i, a, b) for(int i = (a); i >= (b); i -- )
#define ls t[cur].lson
#define rs t[cur].rson
typedef unsigned long long ll;
using namespace std;
const int N = 3e5 + 10;
int n, m;
int head[N], nxt[N << 1], to[N << 1], w[N << 1], E;
int LCA[N], dis[N], dep[N], f[N][19];
struct node
{int x, y, d, lca;
}cm[N];
inline void add(int x, int y, int z)
{to[E] = y;nxt[E] = head[x];w[E] = z;head[x] = E ++;
}
void dfs(int u, int fa)
{for(int i = head[u]; ~i; i = nxt[i]){int x = to[i];if(x == fa) continue;dep[x] = dep[u] + 1, f[x][0] = u;rep(i, 1, 18) f[x][i] = f[f[x][i-1]][i-1];dis[x] = dis[u] + w[i];dfs(x, u);}
}
inline int lca(int x, int y)
{if(dep[x] < dep[y]) swap(x, y);int d = dep[x] - dep[y];repf(i, 18, 0) if( d & (1 << i) ) x = f[x][i];if(x == y) return x;repf(i, 18, 0) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];return f[x][0];
}
inline bool cmp(node n1, node n2) {return n1.d < n2.d;}
int c[N];
void ddd(int u, int fa)
{for(int i = head[u]; ~i; i = nxt[i]){int x = to[i];if(x == fa) continue;ddd(x, u);c[u] += c[x];}
}
inline bool check(int x)
{int l = 1, r = m, best = -1;while(l <= r){int mid = l + r >> 1;if(cm[mid].d > x) r = mid - 1, best = mid;else l = mid + 1;}if(best == -1) return 1;// best ~ mmemset(c, 0, sizeof c);int M = 0;rep(i, best, m) c[cm[i].x] ++, c[cm[i].y] ++, c[cm[i].lca] -= 2, M = max(M, cm[i].d);ddd(1, -1);int MM = 0;rep(i, 1, n) if(c[i] == m - best + 1) MM = max(MM, dis[i] - dis[f[i][0]]);return M - MM <= x;
}
int main()
{ios :: sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(head, -1, sizeof head);cin >> n >> m;rep(i, 1, n - 1){int x, y, z; cin >> x >> y >> z;add(x, y, z); add(y, x, z);}dep[1] = 1; dfs(1, -1);rep(i, 1, m){cin >> cm[i].x >> cm[i].y;cm[i].lca = lca(cm[i].x, cm[i].y);cm[i].d = dis[cm[i].x] + dis[cm[i].y] - 2 * dis[cm[i].lca];}sort(cm + 1, cm + 1 + m, cmp);int l = 0, r = cm[m].d, best = -1;while(l <= r){int mid = l + r >> 1;if(check(mid)) r = mid - 1, best = mid;else l = mid + 1; }cout << best;return 0;
}