洛谷 P2680 運輸計劃 樹鍊剖分+最近公共祖先

題目背景

公元2044年，人類進入了宇宙紀元。

題目描述

公元2044年，人類進入了宇宙紀元。

L L 國有nn個星球，還有 n−1 n − 1 條雙向航道，每條航道建立在兩個球之間，這 n−1 n − 1 條航道連通了 L L 國的所有星球。

小PP掌管一家物流公司，該公司有很多個運輸計劃，每個運輸計劃形如：有一艘物流飛船需要從 ui u i 号星球沿最快的宇航路徑飛行到 vi v i 号星球去。顯然，飛船駛過一條航道是需要時間的，對于航道 j j ，任意飛船駛過它所花費的時間為tjtj，并且任意兩艘飛船之間不會産生任何幹擾。

為了鼓勵科技創新， L L 國國王同意小PP的物流公司參與 L L 國的航道建設，即允許小PP把某一條航道改造成蟲洞，飛船駛過蟲洞不消耗時間。

在蟲洞的建設完成前小 P P 的物流公司就預接了mm個運輸計劃。在蟲洞建設完成後，這 m m 個運輸計劃會同時開始，所有飛船一起出發。當這mm個運輸計劃都完成時，小 P P 的物流公司的階段性工作就完成了。

如果小PP可以自由選擇将哪一條航道改造成蟲洞，試求出小 P P 的物流公司完成階段性工作所需要的最短時間是多少？

輸入輸出格式

輸入格式：

第一行包括兩個正整數n,mn,m，表示 L 國中星球的數量及小 P P 公司預接的運輸計劃的數量，星球從11到 n n 編号。

接下來n−1n−1行描述航道的建設情況，其中第 i i 行包含三個整數 ai,biai,bi和 ti t i ，表示第 i i 條雙向航道修建在aiai與 bi b i 兩個星球之間，任意飛船駛過它所花費的時間為 ti t i 。資料保證

1≤ai,bi≤n 1 ≤ a i , b i ≤ n 且 0≤ti≤1000 0 ≤ t i ≤ 1000 。

接下來 m m 行描述運輸計劃的情況，其中第jj行包含兩個正整數 uj u j 和 vj v j ，表示第 j j 個運輸計劃是從ujuj号星球飛往 vj v j 号星球。

資料保證

1≤ui,vi≤n 1 ≤ u i , v i ≤ n

輸出格式：

一個整數，表示小 P P 的物流公司完成階段性工作所需要的最短時間。

輸入輸出樣例

輸入樣例#1：

6 3

1 2 3

1 6 4

3 1 7

4 3 6

3 5 5

3 6

2 5

4 5

輸出樣例#1：

11

說明

所有測試資料的範圍和特點如下表所示

請注意常數因子帶來的程式效率上的影響。

分析：先用倍增lcalca求出兩點之間的距離。然後把距離從大到小排序，枚舉位置 i i 表示前ii條路徑使用蟲洞，後面的不使用蟲洞的時間來更新答案，即 ans=min(ans,max(len1−w,leni+1)) a n s = m i n ( a n s , m a x ( l e n 1 − w , l e n i + 1 ) ) 。而 w w 為前ii條路徑都共用的邊的權值的最大值。我們可以用線段樹維護區間邊出現的次數最大值，當一條邊出現次數等于 i i 時，維護他的權值最大值。這個可以使用鍊剖解決。因為ww單調減，是以 len1−w l e n 1 − w 單調加，是以當 len1−w>=ans l e n 1 − w >= a n s 即可退掉。

代碼：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

const int maxn=e5+;

using namespace std;

struct node{
    int data,sum;
    int lazy;
}t[maxn*4];

struct edge{
    int y,w,next;
}g[maxn*2];

int n,m,x,y,w,cnt;
int f[maxn][],dep[maxn],dfn[maxn],top[maxn],dis[maxn],size[maxn],ls[maxn],val[maxn],b[maxn];

struct rec{
    int u,v,l;
}a[maxn];

bool cmp(rec x,rec y)
{
    return x.l>y.l;
}

void add(int x,int y,int w)
{
    g[++cnt]=(edge){y,w,ls[x]};
    ls[x]=cnt;
}

void dfs1(int x,int fa)
{
    size[x]=;
    f[x][]=fa;
    for (int i=ls[x];i>;i=g[i].next)
    {
        int y=g[i].y;
        if (y==fa) continue;
        dis[y]=dis[x]+g[i].w;
        dep[y]=dep[x]+;
        val[y]=g[i].w;
        dfs1(y,x);
        size[y]+=size[x];
    }
}

void dfs2(int x,int d)
{
    top[x]=d;
    dfn[x]=++cnt;
    int c=;
    for (int i=ls[x];i>;i=g[i].next)
    {
        int y=g[i].y;
        if (f[x][]==y) continue;
        if (size[y]>size[c]) c=y;
    }
    if (!c) return;
    dfs2(c,d);
    for (int i=ls[x];i>;i=g[i].next)
    {
        int y=g[i].y;
        if ((f[x][]==y) || (y==c)) continue;
        dfs2(y,y);
    }
}

int lca(int x,int y)
{
    if (dep[x]>dep[y]) swap(x,y);
    int d=dep[y]-dep[x],k=,t=<<k;
    while (d)
    {
        if (d>=t) y=f[y][k],d-=t;
        t/=; k--;
    }
    if (x==y) return x;
    k=;
    while (k>=)
    {
        if (f[x][k]!=f[y][k])
        {
            x=f[x][k];
            y=f[y][k];
        }
        k--;
    }
    return f[x][];
}

void build(int p,int l,int r)
{
    if (l==r)
    {
        t[p].data=b[l];
        return;
    }
    int mid=(l+r)/;
    build(p*2,l,mid);
    build(p*2+,mid+,r);
    t[p].data=max(t[p*2].data,t[p*2+].data);
}

void ins(int p,int l,int r,int x,int y,int k)
{
    if ((l==x) && (r==y))
    {
        t[p].sum+=;
        t[p].lazy+=;
        return;
    }
    int mid=(l+r)/;
    if (t[p].lazy)
    {
        t[p*2].lazy+=t[p].lazy;
        t[p*2+].lazy+=t[p].lazy;
        t[p*2].sum+=t[p].lazy;
        t[p*2+].sum+=t[p].lazy;
        t[p].lazy=;
    }
    if (y<=mid) ins(p*2,l,mid,x,y,k);
    else if (x>mid) ins(p*2+,mid+,r,x,y,k);
    else
    {
        ins(p*2,l,mid,x,mid,k);
        ins(p*2+,mid+,r,mid+,y,k);
    }
    t[p].sum=max(t[p*2].sum,t[p*2+].sum);
    t[p].data=;
    if (t[p*2].sum==k) t[p].data=max(t[p].data,t[p*2].data);
    if (t[p*2+].sum==k) t[p].data=max(t[p].data,t[p*2+].data);
}

void change(int x,int y,int k)
{
    while (top[x]!=top[y])
    {
        if (dep[top[x]]>dep[top[y]]) swap(x,y);
        ins(,,n,dfn[top[y]],dfn[y],k);
        y=f[top[y]][];
    }
    if (dep[x]>dep[y]) swap(x,y);
    if (x!=y) ins(,,n,dfn[x]+,dfn[y],k);
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
        add(y,x,w);
    }
    dfs1(,);
    cnt=;
    dfs2(,);
    for (int j=;j<;j++)
    {
        for (int i=;i<=n;i++)
        {
            f[i][j]=f[f[i][j-]][j-];
        }
    }

    for (int i=;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        a[i].l=dis[x]+dis[y]-*dis[lca(x,y)];
        a[i].u=x;
        a[i].v=y;
    }
    sort(a+,a+m+,cmp);
    for (int i=;i<=n;i++) b[dfn[i]]=val[i];
    build(,,n);
    int ans=a[].l;
    for (int i=;i<=m;i++)
    {
        change(a[i].u,a[i].v,i);
        int d=t[].data;
        if (a[].l-d>=ans) break;
        ans=min(ans,max(a[].l-d,a[i+].l));
    }
    printf("%d\n",ans);
}