绫绫,有你的每一天,我都很幸福[大笑][大笑][大笑]
思路
点分治 + 单调队列
01 分数规划 + 长链剖分 + 线段树。
首先看到分数形式求最值先考虑分数规划,二分答案。
现在的问题是:是否存在长度在 \([L, U]\) 之间的树上路径 \(S\) 使得 \(\frac{\sum\limits_{e \in S} v(e)}{|S|} \geq ans\)
化简得 \(\sum\limits_{e \in S} - ans |S| \geq 0\)
可以考虑给树上的每条边权值赋予一个当前二分出的变化量 \(\Delta\),这样直接判定是否存在权值和大于 \(0\) 的路径即可。
树上路径考虑点分治和长剖,这里点分治不好合并,长剖比较好写。
而且点分治常数应该挺大,虽然我的长剖跑不过
因为路径的合法长度是一个区间,所以最后查询答案需要区间查询,考虑用一棵线段树维护。
首先考虑继承答案。
类似重链剖分,考虑处理出每个结点的深子结点,然后按深子结点优先处理出每个结点的 dfs 序。显然一条深链的 dfs 序是连续的。
那么只需要把每个结点的答案存在对应的 dfs 序位置,就可以直接无痛继承了。
当然这里会增加一条边的权值,可以直接把它赋给当前结点的标记,最后从下到上累加标记就行。
考虑如何合并轻子结点的答案。根据长剖的复杂度分析,直接暴力线段树查询合并是可行的。
然后答案就直接分讨有拐点和无拐点的情况维护。
时间复杂度 \(O(n \log^2 n)\)
代码
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef double db;
const int maxn = 1e5 + 5;
const int t_sz = maxn << 2;
const db inf = 1e18;
const db eps = 1e-7;
int n, el, eu, cur;
int dep[maxn], son[maxn], pos[maxn], tow[maxn];
vector<int> g[maxn], w[maxn];
db del, ans;
db f[maxn], tag[maxn];
namespace SGT
{
#define ls (k << 1)
#define rs (k << 1 | 1)
db val[t_sz];
void clear(int k, int l, int r)
{
val[k] = -inf;
if (l == r) return;
int mid = (l + r) >> 1;
clear(ls, l, mid), clear(rs, mid + 1, r);
}
void push_up(int k) { val[k] = max(val[ls], val[rs]); }
void update(int k, int l, int r, int p, db w)
{
if (l == r)
{
val[k] = max(val[k], w);
return;
}
int mid = (l + r) >> 1;
if (p <= mid) update(ls, l, mid, p, w);
else update(rs, mid + 1, r, p, w);
push_up(k);
}
db query(int k, int l, int r, int ql, int qr)
{
if ((l >= ql) && (r <= qr)) return val[k];
int mid = (l + r) >> 1;
db res = -inf;
if (ql <= mid) res = max(res, query(ls, l, mid, ql, qr));
if (qr > mid) res = max(res, query(rs, mid + 1, r, ql, qr));
return res;
}
}
void dfs1(int u, int fa)
{
dep[u] = -1;
for (int i = 0; i < g[u].size(); i++)
{
int v = g[u][i], d = w[u][i];
if (v == fa) continue;
dfs1(v, u);
if (dep[u] < dep[v]) dep[u] = dep[v], son[u] = v, tow[u] = d;
}
dep[u]++;
}
void dfs2(int u, int fa)
{
if (!pos[u]) pos[u] = ++cur;
int pu = pos[u];
tag[pu] = f[pu] = 0;
if (son[u])
{
dfs2(son[u], u);
tag[pu] += tag[pu + 1] + tow[u] - del;
f[pu] = -tag[pu];
}
SGT::update(1, 1, n, pu, f[pu]);
for (int i = 0; i < g[u].size(); i++)
{
int v = g[u][i], d = w[u][i];
if ((v == fa) || (v == son[u])) continue;
dfs2(v, u);
int pv = pos[v];
for (int j = 1; j <= dep[v] + 1; j++)
if (el - j <= dep[u])
{
db val = SGT::query(1, 1, n, pu + max(1, el - j), pu + min(eu - j, dep[u]));
ans = max(ans, f[pv + j - 1] + tag[pu] + tag[pv] + val + d - del);
}
for (int j = 1; j <= dep[v] + 1; j++)
if (d + f[pv + j - 1] + tag[pv] - del > tag[pu] + f[pu + j])
{
f[pu + j] = d + f[pv + j - 1] + tag[pv] - del - tag[pu];
SGT::update(1, 1, n, pu + j, f[pu + j]);
}
}
if (dep[u] >= el) ans = max(ans, tag[pu] + SGT::query(1, 1, n, pu + el, pu + min(eu, dep[u])));
}
bool check(db x)
{
SGT::clear(1, 1, n);
ans = -inf, del = x;
dfs2(1, 0);
return (ans >= 0);
}
int main()
{
scanf("%d%d%d", &n, &el, &eu);
for (int i = 1, u, v, d; i <= n - 1; i++)
{
scanf("%d%d%d", &u, &v, &d);
g[u].push_back(v), w[u].push_back(d);
g[v].push_back(u), w[v].push_back(d);
}
dfs1(1, 0);
db l = 0, r = 1e6;
while (r - l > eps)
{
db mid = (l + r) / 2.0;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.3lf\n", l);
return 0;
}
标签:pu,int,题解,db,mid,dep,tag,WC2010,P4292
From: https://www.cnblogs.com/lingspace/p/p4292.html