#\(\mathcal{\color{red}{Description}}\)

在一棵带有边权的树上，可以选择使一条边权为零。然后对于所有\(M\)条链，使其链长最大值最小。

#\(\mathcal{\color{red}{Solution}}\)

……还是老方法，先分析贪心是否可行\(->\)不可行。再分析状态如何定义\(->\)不可定义。最后看比赛难度\(->NOIP\)。得出结论：不是线性规划而是二分答案

嗯，好的，在这之后我们就可以愉悦地二分答案——二分链长最大值最小值，那我们接下来就要考虑如何\(check\)了。我们思考二分出的最长链的长度之后，我们要找一条大于二分出来的长度的链的公共边，让它变成零——设窝萌二分出的链长是\(k\)，大于\(k\)的链有\(s\)条，那么我们考虑这\(s\)条可能有\(n(0 \leq n \leq m)\)条公共边，我们选择当\(n\)不为零的时候直接选一条最大的公共边，让最长的链减去这条边的权值，观察其是否\(\leq\)我们二分得到的\(k\)，如果是就\(return \ \ 1\)调整\(r\)了；那如果是\(n=0\)，这种方案一定会无从下手，因为作为最终答案来讲，若最短时间为\(T\)，那么所有原来权值大于\(T\)的边一定有起码一条公共边，所以调整\(l\)，直至二分结束即可。

嗯……一二分答案就蒙○……

哦对，链长我们是可以预处理出来的\(qwq\)

#include <cmath>

#include <cstdio>

#include <iostream>

#define MAXN 600010

using namespace std ;

struct edge{

    int to, next, v ;

}e[MAXN] ; int cnt, head[MAXN] ;

int LcA[MAXN], fa[MAXN][32], dep[MAXN], Len[MAXN] ;

int l = 1, r, mid, i, j, A, B, C, N, M, Up, Max, pre, num ;

int dif[MAXN], S[MAXN], T[MAXN], dis[MAXN], edges[MAXN], res, ans ;

inline int qr(){

    int k = 0 ; char c = getchar() ;

    while(!isdigit(c)) c = getchar() ;

    while(isdigit(c)) k = (k << 1) + (k << 3) + c - 48, c = getchar() ;

    return k ;

}

inline void add(int u, int v, int w){

    e[++ cnt].to = v, e[cnt].v = w ;

    e[cnt].next = head[u], head[u] = cnt ;

    e[++ cnt].to = u, e[cnt].v = w ;

    e[cnt].next = head[v], head[v] = cnt ;

}

void _build(int deep, int now, int f){

    fa[now][0] = f ; dep[now] = deep ;

    for(int k = head[now]; k ;k = e[k].next){

        if(e[k].to == f) continue ;

        edges[e[k].to] = e[k].v ;

        Len[e[k].to] = Len[now] + edges[e[k].to] ;

        _build(deep + 1, e[k].to, now) ;

    }

}

inline void _get(int now){

    for(int k = head[now]; k ; k = e[k].next){

        if(e[k].to == fa[now][0]) continue ;

        _get(e[k].to) ;

        dif[now] += dif[e[k].to] ;

    }

    if(dif[now] == num && edges[now] > res) res = edges[now] ;

}

inline void init(){

    Up = log(N) / log(2) + 1 ;

    for(i = 1; i <= Up; i ++)

        for(j = 1; j <= N; j ++)

            fa[j][i] = fa[fa[j][i - 1]][i - 1] ;

}

inline int LCA(int u, int v){

    if(dep[u] < dep[v]) swap(u, v) ;

    pre = dep[u] - dep[v] ;

    for(j = 0; j <= Up; ++ j) if((1 << j) & pre) u = fa[u][j] ;

    if(u == v) return u ;

    for(j = Up; j >= 0; -- j) if(fa[u][j] != fa[v][j]) u = fa[u][j], v = fa[v][j] ;

    return fa[v][0] ;

}

inline bool check(int x){

    fill(dif + 1, dif + N + 1, 0) ; num = 0 ; res = 0 ;

    for(i = 1; i <= M; ++ i)

        if(dis[i] > x)

            num ++, dif[S[i]] ++, dif[T[i]] ++, dif[LcA[i]] -= 2 ;

    _get(1) ;

    if(Max - res > x) return 0 ;

    return 1 ;

}

int main(){

    N = qr(), M = qr() ;

    for(i = 1; i < N; ++ i)

        A = qr(), B = qr(), C = qr(), add(A, B, C);

    _build(1, 1, 0) ; init() ;

    for(i = 1; i <= M; ++ i){

        S[i] = qr(), T[i] = qr(), LcA[i] = LCA(S[i], T[i]) ;

        dis[i] = Len[S[i]] + Len[T[i]] - (Len[LcA[i]] << 1) ;

        Max = max(dis[i], Max) ;

    }

    r = Max  ;

    while(l <= r){

        mid = (l + r) >> 1 ;

        if(check(mid)) r = mid - 1, ans = mid;

        else l = mid + 1 ;

    }

    cout << ans ;

}

本题心得：

\(1\)、有时候单纯暴力的二分不是很好做……但是我们如果换种思路思考二分的话，他的显然性就很显然。

\(2\)、嗯，我还是太弱了，未来的路好长啊……

巴特西

[NOIp2015]运输计划（二分 $+$ 树上差分）

#\(\mathcal{\color{red}{Description}}\)

#\(\mathcal{\color{red}{Solution}}\)

本题心得：

最新文章

热门文章

巴特西

[NOIp2015]运输计划 （二分 $+$ 树上差分）

#\(\mathcal{\color{red}{Description}}\)

#\(\mathcal{\color{red}{Solution}}\)

本题心得：

最新文章

热门文章

[NOIp2015]运输计划（二分 $+$ 树上差分）