题目名称 2652. 秘术「天文密葬法」
输入输出 cdcq_b.in/out
难度等级 ★★★
时间限制 3000 ms (3 s)
内存限制 256 MB
测试数据 20 简单对比
题目来源 2017-04-07
开放分组 全部用户
提交状态
分类标签
长链剖分 01分数规划
通过:26, 提交:146, 通过率:17.81%
Gravatarwzj52501 100 0.345 s C++
Gravatarwzj52501 100 0.500 s C++
GravatarSakits 100 0.506 s C++
GravatarTonyFang 100 0.520 s C++
Gravatarwzj52501 100 0.648 s C++
Gravatarzltttt 100 0.667 s C++
Gravatarfjzzq2002 100 0.676 s C++
GravatarTonyFang 100 0.681 s C++
GravatarAcheing 100 0.727 s C++
GravatarTonyFang 100 0.742 s C++
关于 秘术「天文密葬法」 的讨论
技不如人,甘拜下风。
Gravatarconfoo
2017-04-12 00:24 1楼
技不如人,甘拜下风。
好写不好调的点分治,一上午搭进去了。
Gravatar__stdcall
2017-04-12 12:37 2楼
m=-1表示无限制……
GravatarFoolMike
2017-04-12 12:42 3楼
没有特判,丢了30……真TMD智障
分数规划是什么鬼,我好想只知道下凸包上三分求斜率最小的点……
GravatarFoolMike
2017-04-12 12:59 4楼
技不如人,甘拜下风。
在一些奥妙重重的地方写挂了啊= =
这题可以一个log的
Gravatarfjzzq2002
2017-04-12 13:48 5楼
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;

int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}

#define maxn 200010
#define maxm 400010
#define ool (1ll << 60)
#define LL long long

int n, K, A[maxn], B[maxn], m, head[maxn], nxt[maxm], to[maxm];

void AddEdge(int a, int b) {
to[++m] = b; nxt[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; nxt[m] = head[a]; head[a] = m;
return ;
}

int fa[maxn], son[maxn], mxd[maxn], dep[maxn], pos[maxn], clo;
void build(int u) {
mxd[u] = dep[u];
for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa[u]) {
fa[to[e]] = u;
dep[to[e]] = dep[u] + 1;
build(to[e]);
mxd[u] = max(mxd[u], mxd[to[e]]);
if(!son[u] || mxd[to[e]] > mxd[son[u]]) son[u] = to[e];
}
return ;
}
void gett(int u) {
pos[u] = ++clo;
if(son[u]) gett(son[u]);
for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa[u] && to[e] != son[u]) gett(to[e]);
return ;
}
LL ans, mns[maxn];
void solve(int u, int x) {
if(son[u]) solve(son[u], x);
mns[pos[u]] = A[u] - (LL)x * B[u];
for(int i = 1; i <= mxd[u] - dep[u]; i++) mns[pos[u]+i] += A[u] - (LL)x * B[u];
for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa[u] && to[e] != son[u]) {
solve(to[e], x);
for(int i = 0; i <= min(mxd[to[e]] - dep[to[e]], K); i++)
if(K - i - 1 <= mxd[u] - dep[u])
ans = min(ans, mns[pos[to[e]]+i] + mns[pos[u]+K-i-1]);
for(int i = 0; i <= mxd[to[e]] - dep[to[e]]; i++)
mns[pos[u]+i+1] = min(mns[pos[u]+i+1], mns[pos[to[e]]+i] + A[u] - (LL)x * B[u]);
}
if(K <= mxd[u] - dep[u]) ans = min(ans, mns[pos[u]+K]);
/*printf("leader: %d (now checking %d) %lld\n", u, x, A[u] - (LL)x * B[u]);
for(int i = 0; i <= mxd[u] - dep[u]; i++)
printf("%lld%c", mns[pos[u]+i], i < mxd[u] - dep[u] ? ' ' : '\n'); // */
return ;
}

int main() {
freopen("cdcq_b.in", "r", stdin);
freopen("cdcq_b.out", "w", stdout);

n = read(); K = read();
for(int i = 1; i <= n; i++) A[i] = read() * 2000;
for(int i = 1; i <= n; i++) B[i] = read();
for(int i = 1; i < n; i++) {
int a = read(), b = read();
AddEdge(a, b);
}

if(K < 0) {
double s = (double)ool;
for(int i = 1; i <= n; i++) s = min(s, (double)A[i] / B[i]);
printf("%.2lf\n", s);
return 0;
}

K--;
build(1);
gett(1);
// for(int i = 1; i <= n; i++) printf("%d: [%d] %d %d\n", i, pos[i], dep[i], mxd[i]);
int l = 0, r = 400000000;
while(l < r) {
int mid = l + r >> 1;
ans = ool;
for(int i = 1; i <= n; i++) mns[i] = ool;
solve(1, mid);
if(ans > 0) l = mid + 1; else r = mid;
}
printf("%.2lf\n", l / 2000.0);

return 0;
}

这份代码为何总是编译失败?!求助!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Gravatarxjr
2017-09-16 17:13 6楼

2652. 秘术「天文密葬法」

★★★   输入文件:cdcq_b.in   输出文件:cdcq_b.out   简单对比
时间限制:3 s   内存限制:256 MB


题目说明:

路径的长度是点数

所有整数都是正整数

已添加一句话题意

【题目描述】


永琳需要协助紫解决异变!

在某个满月的夜晚,幻想乡的结界出现了异常,虽然目前还没有找到原因,不过有一点可以肯定的是,这次异变一定和满月有关。间隙妖怪紫在试图修复结界时需要永琳帮她排除满月产生的干扰,为了保护辉夜公主,永琳必须协助紫解决这次异变,所以她打算再次使用符卡"秘术「天文密葬法」"来用虚假的月亮替换真实的满月,但是她在使用符卡的时候出现了一些问题。

"秘术「天文密葬法」"由n个使魔组成,每个使魔都有一个能值和一个波值,同时存在n-1条能量通道将这n个使魔连接起来,并且每个使魔都能通过能量通道和其它所有使魔相连。

完成天文密葬法的关键步骤是在这n个使魔中找到一条用能量通道连接起来的路径,将大部分能量集中于这条路径来展开法术,然而路径上的使魔在法术张开时会产生共振,产生一个干扰值,干扰值等于路径上所有使魔能值的和除以波值的和。

为了确保计划顺利进行,永琳需要选择一条长度为m且干扰值最小的路径,虽然作为月之头脑,但此时永琳需要集中精力展开法术,所以她向你求助。

永琳在知道一个干扰值后就能快速找到这个干扰值对应的路径,你只需要告诉她所有路径中干扰值最小的路径干扰值是多少

答案四舍五入到小数点后两位

一句话题意:

给个树,第i个点有两个权值ai和bi,现在求一条长度为m的路径,使得Σai/Σbi最小


【输入格式】


第一行一个整数n,m,意义如上

如果m为-1则表示对长度没有限制(但路径不能为空

第二行n个整数,第i个整数ai表示第i个使魔的能值

第三行n个整数,第i个整数bi表示第i个使魔的波值

接下来n-1行,每行两个整数l,r,表示有一条能量路径连接第l个使魔和第r个使魔

一行中的所有整数均用空格隔开


【输出格式】


如果不存在长度为m的链,请输出-1

否则一行一个浮点数,表示干扰值最小的路径干扰值是多少


【样例输入1】


3 2

2 3 3

6 6 6

1 2

2 3


【样例输出1】

0.42

【样例输入2】


9 3

9 4 4 1 6 5 1 9 5

8 3 3 1 5 4 1 8 4

1 2

2 3

3 4

3 5

1 6

6 7

7 8

6 9


【样例输出2】

1.15

【数据范围】

数据标号 n m ai,bi
1 <=10 =1 <=200000
2
3 <=1000 <=n
4
5
6
7 <=30000
8
9
10
11
12
13
14
15
16
17 <=200000 =-1
18
19
20