1 条题解
-
0

#include <bits/stdc++.h> #define et(i) (e[i].u ^ e[i].v) #define Max 170734 using namespace std; typedef vector <int> vec; struct edge{ int u, v; double c; edge *read(){scanf("%d%d%lf", &u, &v, &c); return this;} }; int V, inf, sup; int i, j, rt, cx; edge e[Max]; vec g[Max]; // dfs int used[Max], sz[Max], f[Max]; // size of tree, Max size of subtree of node double l, r, m, ans, bnd; // check double pfs[Max], depdis[Max]; // prefix sum, max distance of each depth int dep[Max], que[Max], Mque[Max]; void getCentroid(int x, int _V, int *cen){ vec :: iterator it; int y; sz[x] = 1; f[x] = 0; used[x] = cx; for(it = g[x].begin(); it != g[x].end(); ++it) if(0 <= used[y = x ^ et(*it)] && used[y] != cx){ getCentroid(y, _V, cen); sz[x] += sz[y]; f[x] = max(f[x], sz[y]); } f[x] = max(f[x], _V - sz[x]); if(f[x] < f[*cen]) *cen = x; } bool stcx(int eg0, int eg1){return sz[j ^ et(eg0)] < sz[j ^ et(eg1)];} bool check(int x, double avg){ vec :: iterator it, jt; int h, t, h0, t0; // two queue int y, z, i; // iterator int maxHt = -1, nowHt, unHt; // Max of all height, height of this subtree, allowed union height for(it = g[x].begin(); it != g[x].end(); ++it) if(used[y = x ^ et(*it)] >= 0){ que[0] = y; // bfs used[y] = cx; t = dep[y] = 1; pfs[y] = e[*it].c - avg; for(h = 0; h < t; h++) for(jt = g[z = que[h]].begin(); jt != g[z].end(); ++jt) if(0 <= used[y = z ^ et(*jt)] && used[y] != cx){ // next node que[t++] = y; used[y] = cx; dep[y] = dep[z] + 1; pfs[y] = pfs[z] + (e[*jt].c - avg); } nowHt = dep[que[t - 1]]; // get height of this subtree unHt = maxHt; h0 = t0 = 1; for(i = 0; i < t; i++){ for(z = que[i]; unHt >= 0 && dep[z] + unHt >= inf; unHt--){ for(; h0 < t0 && depdis[unHt] > depdis[Mque[t0 - 1]]; t0--); // keep the queue disdep[Mque[]] monotone Mque[t0++] = unHt; // insert element } for(; h0 < t0 && Mque[h0] + dep[z] > sup; ++h0); // avoid over upperbound if(h0 < t0 && pfs[z] + depdis[Mque[h0]] > -1e-4) return true; // found a path } for(i = maxHt + 1; i <= nowHt; i++) depdis[i] = -INFINITY; // initialize for(i = 0; i < t; i++) depdis[dep[z = que[i]]] = max(depdis[dep[z]], pfs[z]); // update the max distance of this depth maxHt = max(maxHt, nowHt); } return false; // couldn't find a path } void solve(int x){ vec :: iterator it; int y, i; sort(g[j = x].begin(), g[x].end(), stcx); used[x] |= INT_MIN; ++cx; for(l = ans, r = bnd; r - l > 1e-4; ++cx){ m = (l + r) * 0.5; check(x, m) ? l = m : r = m; } ans = l; for(it = g[x].begin(); it != g[x].end(); ++it) if(used[y = x ^ et(*it)] >= 0){ f[rt = 0] = INT_MAX; ++cx; getCentroid(y, sz[y], &rt); if(sz[y] >= inf) solve(rt); } } int main(){ scanf("%d%d%d", &V, &inf, &sup); ans = 0.0; bnd = -INFINITY; for(i = 0; i < V - 1; i++){ e[i].read(); bnd = max(bnd, e[i].c); g[e[i].u].push_back(i); g[e[i].v].push_back(i); } f[rt = 0] = INT_MAX; cx = 1; getCentroid(1, V, &rt); solve(rt); printf("%.3lf\n", ans); return 0; }
- 1
信息
- ID
- 3414
- 时间
- 4000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 1
- 上传者