# NOIP2015运载计划（树上前缀和+LCA+二分）

www.MyException.Cn  网友分享于：2013-10-22  浏览：0次
NOIP2015运输计划（树上前缀和+LCA+二分）

## Description

L 国有 n 个星球，还有 n−1 条双向航道，每条航道建立在两个星球之间，这 n−1 条航道连通了 L 国的所有星球。

6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5

11

## Code

``````#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define N 300010
using namespace std;

struct plan
{
int u, v, lca, dis;
} node[N];
struct info {
int to, nex, w;
} e[N * 2];
int n, m, head[N * 2], tot;
int l, r, edge[N];
bool vis[N];
int _log, fa[N][19], dep[N], dis[N];

inline int read() {
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-')f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}

inline void add_edge(int u, int v, int w) {
e[++tot].to = v;
e[tot].w = w;
}

void dfs(int u) {
vis[u] = 1;

for (int i = 1; i <= _log; ++i)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (int i = head[u]; i; i = e[i].nex) {
int v = e[i].to;
if (vis[v]) continue;
edge[v] = i;
dep[v] = dep[u] + 1;
fa[v][0] = u;
dis[v] = dis[u] + e[i].w;
dfs(v);
}
}

int LCA(int u, int v) {
if (dep[u] > dep[v]) swap(u, v);
int d = dep[v] - dep[u];

for (int i = 0; i <= _log; ++i)
if (d & (1 << i))
v = fa[v][i];

if (u == v) return u;

for (int i = _log; i >= 0; i--)
if (fa[u][i] != fa[v][i]) {
u = fa[u][i];
v = fa[v][i];
}

return fa[u][0];
}

int sum[N];
void update(int u, int fa) {
for (int i = head[u]; i; i = e[i].nex) {
int v = e[i].to;
if (v == fa) continue;
update(v, u);
sum[u] += sum[v];
}
}

bool pd(int mid) {
int tot = 0, dec = 0;
memset(sum, 0, sizeof(sum));
for (int i = 1; i <= m; ++i)
if (node[i].dis > mid) {
tot++;
dec = max(dec, node[i].dis - mid);
sum[node[i].u]++;
sum[node[i].v]++;
sum[node[i].lca] -= 2;
}
update(1, 1);
for (int i = 1; i <= n; ++i)
if (sum[i] == tot && e[edge[i]].w >= dec) return 1;
return 0;
}

int main() {
_log = log(n) / log(2);
for (int i = 1; i < n; ++i) {
int u = read(), v = read(), w = read();
}
dfs(1);

for (int i = 1; i <= m; ++i) {
int u = read(), v = read();
node[i].u = u, node[i].v = v;
node[i].lca = LCA(u, v);
node[i].dis = (dis[u] + dis[v]) - 2 * dis[node[i].lca];
r = max(r, node[i].dis);
}
int Ans;
while (l <= r) {
int mid = (l + r) >> 1;
if (pd(mid))
Ans = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d\n", Ans);
return 0;
}``````