http://codevs.cn/problem/1218/

比较显然的倍增,但是对于跨过根需要很多讨论,总体思路是贪心。

写了一上午,不想再说什么了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 100003;
int in() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = (k << 3) + (k << 1) + c - '0';
return k * fh;
} struct node {int nxt, to, w;} E[N << 1];
struct data {
ll left; int from;
bool operator < (const data &A) const {
return left < A.left;
}
} A[N], B[N];
struct data2 {
int id, dis;
bool operator < (const data2 &A) const {
return dis < A.dis;
}
} P[N];
int f[N][18], n, m, cnt = 0, point[N], L[N], R[N], w[N], Army[N], a[N], nxt[N], upto[N];
ll c[N][18];
bool mark[N]; void ins(int u, int v, int w) {E[++cnt] = (node) {point[u], v, w}; point[u] = cnt;} void dfs(int x) {
L[x] = ++cnt;
w[cnt] = x;
for(int i = point[x]; i; i = E[i].nxt)
if (E[i].to != f[x][0]) {
f[E[i].to][0] = x;
c[E[i].to][0] = E[i].w;
dfs(E[i].to);
}
R[x] = cnt;
} void pushup_mark(int x) {
if (mark[x]) return;
bool flag = false, marknow = true;
for(int i = point[x]; i; i = E[i].nxt)
if (E[i].to != f[x][0]) {
pushup_mark(E[i].to);
flag = true;
marknow &= mark[E[i].to];
}
if (flag) mark[x] = marknow;
} bool cmp_forMrazer(data X, data Y) {
return X.from == Y.from ? X.left < Y.left : X.from < Y.from;
} bool can(ll up) {
int tmp, tot = 0, tot2 = 0, tot3 = 0; ll ret;
memset(mark, 0, sizeof(bool) * (n + 1));
for(int i = 1; i <= m; ++i) {
ret = up; tmp = Army[i];
for(int j = 17; j >= 0; --j)
if (f[tmp][j] && f[tmp][j] != 1 && c[tmp][j] <= ret) {
ret -= c[tmp][j];
tmp = f[tmp][j];
}
if (c[tmp][0] <= ret) A[++tot] = (data) {ret - c[tmp][0], tmp};
else mark[tmp] = true;
} // for(int i = 1; i <= tot; ++i) printf("left = %I64d from = %d\n", A[i].left, A[i].from); for(int i = point[1]; i; i = E[i].nxt)
pushup_mark(E[i].to); stable_sort(A + 1, A + tot + 1, cmp_forMrazer); for(int i = 1; i <= tot; ++i)
if (!mark[A[i].from])
if (A[i].left <= c[A[i].from][0])
mark[A[i].from] = true;
else
B[++tot3] = A[i];
else
B[++tot3] = A[i];
// printf("%d\n", tot3);
// for(int i = 1; i <= tot3; ++i) printf("left = %I64d from = %d\n", B[i].left, B[i].from); for(int i = point[1]; i; i = E[i].nxt)
if (!mark[E[i].to])
P[++tot2] = (data2) {E[i].to, c[E[i].to][0]}; stable_sort(B + 1, B + tot3 + 1);
stable_sort(P + 1, P + tot2 + 1); // printf("%d %d\n", tot3, tot2); if (tot3 < tot2) return false;
for(; tot3 && tot2; --tot3, --tot2)
if (B[tot3].left < P[tot2].dis) return false;
return true;
} int main() {
n = in();
int u, v, w;
for(int i = 1; i < n; ++i) {
u = in(); v = in(); w = in();
ins(u, v, w);
ins(v, u, w);
} dfs(1);
for(int j = 1; j <= 17; ++j)
for(int i = 1; i <= n; ++i) {
f[i][j] = f[f[i][j - 1]][j - 1];
if (f[i][j]) c[i][j] = c[i][j - 1] + c[f[i][j - 1]][j - 1];
}
m = in();
for(int i = 1; i <= m; ++i) Army[i] = in();
ll left = 0, right = 50000000000000ll, mid;
while (left < right) {
mid = (left + right) >> 1; //printf("left = %I64d mid = %I64d right = %I64d\n", left, mid, right);
if (can(mid)) right = mid;
else left = mid + 1;
} printf("%lld\n", left);
return 0;
}

_(:з」∠)_

最新文章

  1. Atitit 输入法原理与概论ati use
  2. 通过代码自定义cell(cell的高度不一致,比如微博)
  3. 【Linux学习】Linux下用户组、文件权限详解
  4. Source Insight 3.X 标签插件v1.0发布
  5. Three.js资源
  6. Sleep函数的真正用意
  7. PB中获取datawindow提交的sql语句
  8. Netty那点事
  9. 非IE内核浏览器支持activex插件
  10. BZOJ 1087 互不侵犯
  11. hyper中安装wdOS-1.0-x86_64(wdlinux)遇到的网卡问题
  12. MATLAB中digits和vpa
  13. Gym 100952F&amp;&amp;2015 HIAST Collegiate Programming Contest F. Contestants Ranking【BFS+STL乱搞(map+vector)+优先队列】
  14. [Swift]LeetCode324. 摆动排序 II | Wiggle Sort II
  15. 堡垒机jumpserver测试记录--安装
  16. Android Studio: Application Installation Failed
  17. 探索未知种族之osg类生物---器官初始化二
  18. centos chroot使用
  19. 移动web开发(四)——X-UA-Compatible
  20. Python处理海量数据的实战研究

热门文章

  1. TestNG之注解的生命周期
  2. 手机开启HDR后拍照有什么不同?
  3. jmeter 与 java http
  4. CSS中单位px和em,rem的区别
  5. 解决为什么每次打开Eclipse新的workspace需要更新nexus-maven-repository-index问题
  6. [No000060]冷读热读:读书九问
  7. NOI2004 郁闷的出纳员
  8. PAT 1015. 德才论 (25) JAVA
  9. 安装 SQL SERVER 2008 必须使用 &quot;角色管理工具&quot; 错误 的 解决方案 (转)
  10. tar 解压缩命令详解