【NOIP2015】洛谷2680 運輸計劃【解法一】

題目背景

公元 2044 年,人類進入了宇宙紀元。 題目描述

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

小 P 掌管一家物流公司,該公司有很多個運輸計劃,每個運輸計劃形如:有一艘物

流飛船需要從 ui 号星球沿最快的宇航路徑飛行到 vi 号星球去。顯然,飛船駛過一條航道 是需要時間的,對于航道

j,任意飛船駛過它所花費的時間為 tj,并且任意兩艘飛船之 間不會産生任何幹擾。

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

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

個運輸計劃都完成時,小 P 的 物流公司的階段性工作就完成了。

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

首先可以二分答案，對于每一個時間，找到所有用時超過他的【也就是需要使用蟲洞的】路徑，然後隻要檢查是否有一條邊被這些所有路徑都覆寫且長度不小于需要的長度【需要的長度即為最長路徑減去二分的時間】。

檢查的另一個做法見【這裡】。

找到這些路徑中最低的【深度最深的】LCA記為x，然後檢查是否所有路徑都至少有一個端點在x的子樹裡，如果有一條路徑沒有，那麼這條路徑和以x為LCA的這條路徑一定沒有公共邊。否則的話，按隻有一個端點在和兩個端點都在【這樣的話他的LCA就是x】分類記錄。對于隻有一個端點在的路徑隻有一種取法，兩個端點都在的路徑可以驗證一下取哪個端點會使新LCA 盡可能低。求出這些所有端點的LCA記為y，那麼所有路徑的重疊部分就是y->x。再求路徑上最長邊即可。如果沒有隻有一個端點在子樹裡的路徑，隻需要枚舉第一個路徑取哪個點，後面照常。

檢查每個詢問是否有端點在子樹裡和求這些點的LCA都是O(mlogn)的，是以總的時間複雜度是O(mlog(nl)logn)。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mx=;
int n,m,p[][],fir[],to[],len[],ne[],anc[][],
dis[][],maxlen[][],ans[],anslca[],dep[],
g[][],f[];
bool flag[];
int rd()
{
    int x=;
    char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9')
    {
        x=x*+c-'0';
        c=getchar();
    }
    return x;
}
void add(int num,int u,int v,int l)
{
    ne[num]=fir[u];
    fir[u]=num;
    to[num]=v;
    len[num]=l;
}
void init()
{
    int i,x,y,z;
    n=rd();
    m=rd();
    for (i=;i<n;i++)
    {
        x=rd();
        y=rd();
        z=rd();
        add(i*,x,y,z);
        add(i*+,y,x,z);
    }
    for (i=;i<=m;i++)
    {
        p[i][]=rd();
        p[i][]=rd();
    }
}
void dfs(int u,int fa)
{
    int i,v;
    for (i=fir[u];i;i=ne[i])
      if ((v=to[i])!=fa)
      {
        dep[v]=dep[u]+;
        anc[v][]=u;
        dis[v][]=maxlen[v][]=len[i];
        dfs(v,u);
      }
}
void pre()
{
    int i,j,k,u,v;
    dep[]=;
    dfs(,-);
    for (k=;k<=mx;k++)
      for (i=;i<=n;i++)
      {
        anc[i][k]=anc[anc[i][k-]][k-];
        dis[i][k]=dis[i][k-]+dis[anc[i][k-]][k-];
        maxlen[i][k]=max(maxlen[i][k-],maxlen[anc[i][k-]][k-]);
      }
    for (i=;i<=m;i++)
    {
        u=p[i][];
        v=p[i][];
        if (dep[u]<dep[v]) swap(u,v);
        for (k=mx;k>=;k--)
          if (dep[u]-(<<k)>=dep[v])
          {
            ans[i]+=dis[u][k];
            u=anc[u][k];
          }
        if (u==v)
        {
            anslca[i]=u;
            continue;
        }
        for (k=mx;k>=;k--)
          if (anc[u][k]!=anc[v][k])
          {
            ans[i]+=dis[u][k]+dis[v][k];
            u=anc[u][k];
            v=anc[v][k];
          }
        ans[i]+=dis[u][]+dis[v][];
        anslca[i]=anc[u][];
    }
}
int lca(int u,int v)
{
    int k,i;
    if (dep[u]<dep[v]) swap(u,v);
    for (k=mx;k>=;k--)
      if (dep[u]-(<<k)>=dep[v])
        u=anc[u][k];
    if (u==v) return u;
    for (k=mx;k>=;k--)
      if (anc[u][k]!=anc[v][k])
      {
        u=anc[u][k];
        v=anc[v][k];
      }
    return anc[u][];
}
bool ok(int x)
{
    int i,j,k,u,v,totf=,totg=,lowest=-,lca1,temp,need=;
    for (i=;i<=m;i++)
      if (ans[i]>x)
      {
        need=max(need,ans[i]-x);
        flag[i]=;
        if (lowest==-||dep[anslca[i]]>dep[lowest])
          lowest=anslca[i];
      }
      else flag[i]=;
    for (i=;i<=m;i++)
      if (flag[i])
      {
        if (anslca[i]==lowest)
        {
            totg++;
            g[totg][]=p[i][];
            g[totg][]=p[i][];
        }
        else
        {
            if (lca(lowest,p[i][])==lowest) f[++totf]=p[i][];
            else
            {
                if (lca(lowest,p[i][])==lowest) f[++totf]=p[i][];
                else return ;
            }
        }
      }
    if (totf)
    {
        lca1=f[];
        for (i=;i<=totf;i++)
          lca1=lca(lca1,f[i]);
        for (i=;i<=totg;i++)
        {
            u=lca(lca1,g[i][]);
            v=lca(lca1,g[i][]);
            if (dep[u]<dep[v]) lca1=v;
            else lca1=u;
        }
        temp=;
        for (k=mx;k>=;k--)
          if (dep[lca1]-(<<k)>=dep[lowest])
          {
            temp=max(temp,maxlen[lca1][k]);
            lca1=anc[lca1][k];
          }
        return temp>=need;
    }
    else
    {
        lca1=g[][];
        for (i=;i<=totg;i++)
        {
            u=lca(lca1,g[i][]);
            v=lca(lca1,g[i][]);
            if (dep[u]<dep[v]) lca1=v;
            else lca1=u;
        }
        temp=;
        for (k=mx;k>=;k--)
          if (dep[lca1]-(<<k)>=dep[lowest])
          {
            temp=max(temp,maxlen[lca1][k]);
            lca1=anc[lca1][k];
          }
        if (temp>=need) return ;
        lca1=g[][];
        for (i=;i<=totg;i++)
        {
            u=lca(lca1,g[i][]);
            v=lca(lca1,g[i][]);
            if (dep[u]<dep[v]) lca1=v;
            else lca1=u;
        }
        temp=;
        for (k=mx;k>=;k--)
          if (dep[lca1]-(<<k)>=dep[lowest])
          {
            temp=max(temp,maxlen[lca1][k]);
            lca1=anc[lca1][k];
          }
        if (temp>=need) return ;
    }
    return ;
}
void solve()
{
    int i,temp,l,r,mid;
    temp=;
    for (i=;i<=m;i++)
      temp=max(temp,ans[i]);
    l=;
    r=temp;
    while (l<r)
    {
        mid=(l+r)/;
        if (ok(mid)) r=mid;
        else l=mid+;
    }
    printf("%d\n",l);
}
int main()
{
    init();
    pre();
    solve();
}