【NOIP 2015 DAY2 T3】运输计划（树链剖分-LCA）

题目背景

公元 2044 年,人类进入了宇宙纪元。

题目描述

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

小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物

流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后, 这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?

输入输出格式

输入格式：

输入文件名为 transport.in。

第一行包括两个正整数 n、m,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 1 到 n 编号。

接下来 n-1 行描述航道的建设情况,其中第 i 行包含三个整数 ai, bi 和 ti,表示第

i 条双向航道修建在 ai 与 bi 两个星球之间,任意飞船驶过它所花费的时间为 ti。

接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j个运输计划是从 uj 号星球飞往 vj 号星球。

输出格式：

输出共1行,包含1个整数,表示小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
说明

所有测试数据的范围和特点如下表所示

请注意常数因子带来的程序效率上的影响。

【分析】

　　这题，像是很多解法哦。

　　首先是，你是选大的那几条链删掉公共边，就是树链的交，然后维护一个最大值【可是我不会树链的交【如果没有交链直接break就好了

　　我打的是二分版本。　　

　　先预处理每条路径的LCA，二分答案，如果某条路径的长度大于这个二分答案，那么意味着他里面一定要割掉一条边嘛，

　　那么，把这样的路径记录下来（那个，是一个很妙的方法，在x，y上标记1，在lca上标记-2，子树的sum就是它的访问次数，我们判断的时候只需要dfs一遍，回溯累加就好了）

　　我们只能选择涵盖所有不合法路径的边减掉，取他们之中的max当然是更好的，然后看看这个max能不能使路径合法。

　　【为什么我打的nlogxx比别人的暴力还慢【捂脸= =

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 using namespace std;

 #define Maxn 300010

 #define LL long long

 struct node

 {

     int x,y,c,next;

 }t[Maxn*];int len;

 int n,m;

 int first[Maxn];

 int ax[Maxn],ay[Maxn],lca[Maxn];

 LL h[Maxn],ln[Maxn];

 void ins(int x,int y,int c)

 {

     t[++len].x=x;t[len].y=y;t[len].c=c;

     t[len].next=first[x];first[x]=len;

 }

 LL mymax(LL x,LL y) {return x>y?x:y;}

 int dep[Maxn],dfn[Maxn],sm[Maxn],son[Maxn];

 int fa[Maxn],w[Maxn];

 void dfs1(int x,int f)

 {

     dep[x]=dep[f]+;sm[x]=;son[x]=;

     fa[x]=f;

     for(int i=first[x];i;i=t[i].next) if(t[i].y!=f)

     {

         int y=t[i].y;

         w[y]=t[i].c;

         dfs1(y,x);

         sm[x]+=sm[y];

         if(sm[y]>sm[son[x]]) son[x]=y;

     }

 }

 int tp[Maxn],cnt=;

 void dfs2(int x,int tpp)

 {

     dfn[x]=++cnt;h[cnt]=h[cnt-]+w[x];

     tp[x]=tpp;

     if(son[x]) dfs2(son[x],tpp);

     for(int i=first[x];i;i=t[i].next) if(t[i].y!=fa[x]&&t[i].y!=son[x])

     {

         int y=t[i].y;

         dfs2(y,y);

     }

 }

 void ffind(int id,int x,int y)

 {

     int tt;

     while(tp[x]!=tp[y])

     {

         if(dep[tp[x]]<dep[tp[y]]) tt=x,x=y,y=tt;

         ln[id]+=h[dfn[x]]-h[dfn[tp[x]]-];

         x=fa[tp[x]];

     }

     if(dep[x]<dep[y]) tt=x,x=y,y=tt;

     ln[id]+=h[dfn[x]]-h[dfn[y]];

     lca[id]=y;

 }

 int tot[Maxn];

 int les(int x,int tt)

 {

     int ans=-;

     for(int i=first[x];i;i=t[i].next) if(t[i].y!=fa[x])

     {

         int y=t[i].y;

         int now=les(y,tt);

         tot[x]+=tot[y];

         if(now!=-) ans=mymax(ans,now);

     }

     if(tot[x]==tt) ans=mymax(ans,w[x]);

     return ans;

 }

 bool check(LL mid)

 {

     memset(tot,,sizeof(tot));

     LL mx=;int tt=;

     for(int i=;i<=m;i++) if(ln[i]>mid)

     {

             tot[ax[i]]++;tot[ay[i]]++;

             tot[lca[i]]-=;

         mx=mymax(mx,ln[i]);

         tt++;

     }

     int now=les(,tt);

     if(now==-||mx-now>mid) return ;

     return ;

 }

 void get_ans(LL l,LL r)

 {

     while(l<r)

     {

         LL mid=(l+r)/;

         if(check(mid)) r=mid;

         else l=mid+;

     }

     printf("%lld\n",l);

 }

 int main()

 {

     LL mx=;

     scanf("%d%d",&n,&m);

     len=;

     memset(first,,sizeof(first));

     for(int i=;i<n;i++)

     {

         int x,y,c;

         scanf("%d%d%d",&x,&y,&c);

         ins(x,y,c);ins(y,x,c);

     }

     dep[]=;

     dfs1(,);h[]=;

     dfs2(,);

     for(int i=;i<=m;i++)

     {

         scanf("%d%d",&ax[i],&ay[i]);

         ffind(i,ax[i],ay[i]);

         mx=mymax(mx,ln[i]);

     }

     get_ans(,mx);

     return ;

 }

2016-11-15 16:41:22

巴特西

【NOIP 2015 DAY2 T3】运输计划（树链剖分-LCA）

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章

巴特西

【NOIP 2015 DAY2 T3】 运输计划 （树链剖分-LCA）

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章

【NOIP 2015 DAY2 T3】运输计划（树链剖分-LCA）