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;
}
_(:з」∠)_