[WC2010]重建计划 题解
题目地址:洛谷:【P4292】[WC2010]重建计划 – 洛谷、BZOJ:Problem 1758. — [Wc2010]重建计划
题目描述
题意简述
给你一棵树,求长度在[L, U]范围内的树链的边权平均值的最大值。
输入输出格式
输入格式:
第一行包含一个正整数N,表示X国的城市个数。
第二行包含两个正整数L、U,表示政府要求的第一期重建方案中修建道路数的上下限。
接下来的N-1行描述重建小组的原有方案,每行三个正整数ai, bi, vi,分别表示道路(ai, bi),其价值为vi。其中城市由1…N标号。
输出格式:
仅包含一行,为一个实数AvgValue,即最大平均价值。
小数点后保留三位。
输入输出样例
输入样例#1:
4 2 3 1 2 1 1 3 2 1 4 3
输出样例#1:
2.500
说明
新方案中选择路径(3, 1), (1, 4)可以得到的平均价值为2.5,为最大平均价值。
对于20%的数据,N ≤ 5 000;
另有30%的数据,N ≤ 100 000, 原有方案恰好为一条路径(链);
对于100%的数据,N ≤ 100 000, 1 ≤ L ≤ U ≤ N-1, vi ≤ 10^6。
题解
整个树找树链可以考虑使用点分治。
对于每个重心,我们考虑二分答案,验证的时候找两条子树到重心的路径拼起来长度在范围内的,或者一条路径长度就在范围内的,在处理边权和的时候在每个边权上减掉答案,则只需要判断边权和是否不小于0即可。
由于对于以前找到过的每一个深度的链,只需要存下边权和最大值,就可以直接拿来判断了。而枚举每个深度去遍历合法区间,会造成复杂度退化为$O(n^2)$。我们考虑单调队列优化这一过程,从浅到深枚举当前遍历子树的每个节点,对应的在以前找到过的深度区间可以确定为[L-d, R-d],由于遍历的顺序单调,单调队列可以倒着从深到浅维护最大值来判定,遍历节点时使用BFS,这样节点的遍历顺序就是从浅到深单调的了,这样判定的复杂度是$O(n)$的了。
单调队列的复杂度其实应该是$O(之前找到过的最大深度)$的,因此,我们可以对每一棵子树的深度进行排序,从浅的子树开始遍历,可以优化时间,不过我采用了快排,排序复杂度会多一个$\log n$。
另外,本题有一定的卡常数成分,有以下几个卡常的地方可以作为参考:
- 每次遍历需要初始化最大值数组,可以到用的时候再初始化(参见121~123行);
- 对于大小小于L的子树,是找不到符合条件的链的,因此可以不用递归下去处理(参见145行);
- 可以使用计数排序代替快排(没写);
- 读入优化,fread(我的文件头);
- 存树用邻接表而不是vector;
- 自己实现的max函数代替STL的;
- 手写BFS的队列;
- 二分答案的时候,可以将左端点设为已经找到的解,右端点设为最大边权,这样每次二分只会去找比当前解更优的解更新。
代码
// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
return res * neg;
}
inline int max(int a, int b) {
return a > b ? a : b;
}
inline double max(double a, double b) {
return a > b ? a : b;
}
const int MAXN = 100005;
const double EPS = 1e-4;
int n, L, U;
double ans;
struct Edge {
int to, w, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;
inline void addedge(int u, int v, int w) {
gra[tot] = Edge {v, w, head[u]}; head[u] = tot++;
gra[tot] = Edge {u, w, head[v]}; head[v] = tot++;
}
bool vis[MAXN];
int siz[MAXN], rt, rtsiz;
inline void findrt(int u, int fa, int tot) {
siz[u] = 1; int msiz = 0;
for(register int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(vis[v] || v == fa) continue;
findrt(v, u, tot);
siz[u] += siz[v];
msiz = max(msiz, siz[v]);
}
msiz = max(msiz, tot - siz[u]);
if(msiz < rtsiz) {
rt = u; rtsiz = msiz;
}
}
int fa[MAXN], dep[MAXN], que[MAXN], deq[MAXN];
double dis[MAXN];
int tdep[MAXN], subt[MAXN], subw[MAXN], stot;
inline bool cmp(int a, int b) {
return tdep[a] < tdep[b];
}
inline int dfs(int u, int fa, int dep) {
int mxdep = dep;
for(register int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(vis[v] || v == fa) continue;
mxdep = max(mxdep, dfs(v, u, dep + 1));
}
return mxdep;
}
double mx[MAXN];
inline bool check(int u, double mid) {
int mxdep = 0;
stot = 0;
for(register int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
subt[++stot] = v;
subw[v] = gra[i].w;
tdep[v] = dfs(v, u, 1);
}
std::sort(subt + 1, subt + stot + 1, cmp);
for(register int i = 1; i <= stot; i++) {
int v = subt[i];
if(vis[v]) continue;
int hd = 0, tl = 1; fa[v] = u; dep[v] = 1; dis[v] = subw[v] - mid; que[0] = v;
while(hd < tl) {
int uu = que[hd++];
for(register int j = head[uu]; ~j; j = gra[j].nxt) {
int vv = gra[j].to;
if(vis[vv] || vv == fa[uu]) continue;
fa[vv] = uu;
dep[vv] = dep[uu] + 1;
dis[vv] = dis[uu] + gra[j].w - mid;
que[tl++] = vv;
}
}
int l = 1, r = 0, now = mxdep;
for(register int j = 0; j < tl; j++) {
int p = que[j];
while(dep[p] + now >= L && now >= 0) {
while(l <= r && mx[deq[r]] < mx[now]) r--;
deq[++r] = now; now--;
}
while(l <= r && dep[p] + deq[l] > U) l++;
if(l <= r && dis[p] + mx[deq[l]] + EPS >= 0) return true;
}
for(register int j = mxdep + 1; j <= dep[que[tl - 1]]; j++) {
mx[j] = -1e9;
}
for(register int j = 0; j < tl; j++) {
int p = que[j];
mx[dep[p]] = max(mx[dep[p]], dis[p]);
}
mxdep = max(mxdep, dep[que[tl - 1]]);
}
return false;
}
int lim;
inline void divide(int u) {
register double l = ans, r = lim, mid;
while(r - l > EPS) {
mid = (l + r) / 2;
if(check(u, mid)) l = mid; else r = mid;
}
ans = l;
vis[u] = true;
for(register int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(vis[v] || siz[v] < L) continue;
rt = 0; rtsiz = n; findrt(v, u, siz[v]);
divide(rt);
}
}
int main() {
memset(head, -1, sizeof(head));
n = readint(); L = readint(); U = readint();
for(register int i = 1, a, b, c; i < n; i++) {
a = readint(); b = readint(); c = readint();
lim = max(lim, c);
addedge(a, b, c);
}
rt = 0; rtsiz = n; findrt(1, 0, n);
divide(rt);
printf("%.3lf", ans);
return 0;
}