[NOIP2015]运输计划
"守得云开见月明"
题目大意:给出一颗树,若干个起点和终点,可以消去一条边的边权,要求起点到终点的最短路径中最长的一条能有多短.
本来想树剖??维护最大值和链长,然后并不懂怎么二分.看了看发现可以用(lca)啊蠢猪(做的题太少了),尝试了树剖(lca),好写还快.
而二分的策略是这样的,你要删去的边肯定是当前最大路径中的一条边,虽然我们不知道这条路径包含最大的边是多少,但是取当前树中的最长边已经足够把初始的左右边界缩小很多了.然后我们取(mid),进行(check),那(check)的规则是这样的:
-
取每一条路径的长度,和(mid)比较,如果小于,则忽略,因为完全不用改变,如果大于,则需要进行一点标记,将(s)和(t)的(lca)的标记(-2),(s)和(t)标记分别(+1),然后(tot+1)
-
按照(dfs)序倒序遍历,保证父亲先继承所有儿子结点的标记数,然后要判断父边和当前的二分出的长度的关系,以及点的标记数是否等于(tot),两者都满足,则返回(true),否则继续循环,循环结束,返回(false).
为什么这样的策略正确呢?因为首先你只能消去一条边的权值,也就是比当前二分出的答案还要大的路径中都要消去同一条包含的边,且消去后满足这些边都可以比当前最大值最小小.
因为是在树上,我们完全可以用点来表示边.树上差分来判断这条边是否都被包含.也就是父亲继承儿子的标记,
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using std::max;
const int N = 300007;
struct Edge{
int to, val, next;
}e[N << 1];
int n, m, cnt, dfs_clock, e_max, d_max, ans;
int q[N], f[N], head[N], fa[N], top[N], deep[N], son[N], size[N], val[N], anc[N], s[N], t[N];
int cost[N], dis[N];
inline void addedge(int x, int y, int z){
++cnt;
e[cnt].to = y;
e[cnt].val = z;
e[cnt].next = head[x];
head[x] = cnt;
}
inline int read() {//读入优化
int re = 0;
char ch = getchar();
while (ch <'0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9'){
re = re * 10 + ch - '0';
ch = getchar();
}
return re;
}
void dfs_1(int u, int father, int depth){
size[u] = 1, son[u] = 0, fa[u] = father, deep[u] = depth;
for(int i = head[u], v; i; i = e[i].next){
v = e[i].to;
if(v == father) continue;
val[v] = val[u] + e[i].val;
dfs_1(v, u, depth + 1);
cost[v] = e[i].val;
size[u] += size[v];
if(size[v] > size[son[u]]){
son[u] = v;
}
}
return;
}
void dfs_2(int u, int tp){
q[++dfs_clock] = u, top[u] = tp;
if(son[u]) dfs_2(son[u], tp);
for(int i = head[u], v; i; i = e[i].next){
v = e[i].to;
if(v == fa[u] || v == son[u]) continue;
dfs_2(v, v);
}
return;
}
inline int lca(int x, int y){
while(top[x] != top[y]){
if(deep[top[x]] >= deep[top[y]]) x = fa[top[x]];
else y = fa[top[y]];
}
if(deep[x] < deep[y]) return x; return y;
}
inline bool check(int fff){
memset(f, 0, sizeof(f));
int tot = 0;
for(int i = 1; i <= m; ++i){
if(dis[i] > fff){
f[s[i]]++, f[t[i]]++, f[anc[i]] -= 2, tot++;
}
}
for(int i = n; i; --i){
f[fa[q[i]]] += f[q[i]];
if(cost[q[i]] >= d_max - fff && f[q[i]] == tot){
return true;
}
}
return false;
}
int main(){
n = read(), m = read();
int la, lb, lc;
for(int i = 1; i <= n - 1; ++i){
la = read(), lb = read(), lc = read();
addedge(la, lb, lc);
addedge(lb, la, lc);
e_max = max(e_max, lc);
}
dfs_1(1, 0, 0);
dfs_2(1, 1);
for(int i = 1; i <= m; ++i){
s[i] = read(), t[i] = read();
anc[i] = lca(s[i], t[i]);
dis[i] = val[s[i]] + val[t[i]] - val[anc[i]] * 2;
d_max = max(d_max, dis[i]);
}
int l = d_max - e_max, r = d_max, mid;
while(l <= r){
mid = l + ((r - l) >> 1);
if(check(mid)){
r = mid - 1;
ans = mid;
}
else l = mid + 1;
}
printf("%d
", ans);
return 0;
}