bzoj4326 NOIP2015 运输计划

　　二分答案，如果一条航道的长度大于当前二分的答案，那么很明显这条航道上需要有一条边权值变为0，且条边权值应该>=(航道长度-二分的答案),那么若想使得所以不满足条件的航道都满足条件，这个虫洞就应该设置在这些航道的交集上，且权值应>=(max(航道长度)-二分的答案),航道的交集具体实现可以把这条航道上路径次数都加1，假设不满足条件的航道有m条，那么一条边如果次数==m条，就表示其是m条航道的交集了，实现的话一个dfs就可以搞定，复杂度O(nlogn)

　　代码

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<vector>
  4 #include<set>
  5 #define pb push_back
  6 #define N 700100
  7 using namespace std;
  8 int dp,pre[N],p[N],tt[N],ww[N],fa[N],deep[N],v[N],A[N],B[N],LCA[N];
  9 int s[N][20],n,m,a,b,c,i,sum[N],ans,cnt,dis[N],dist[N];
 10 void link(int x,int y,int z)
 11 {
 12     dp++;pre[dp]=p[x];p[x]=dp;tt[dp]=y;ww[dp]=z;
 13 }
 14 void dfs(int x)
 15 {
 16     int i;
 17     i=p[x];
 18     while (i)
 19     {
 20         if (tt[i]!=fa[x])
 21         {
 22             deep[tt[i]]=deep[x]+1;
 23             fa[tt[i]]=x;
 24             v[tt[i]]=ww[i];
 25             dis[tt[i]]=dis[x]+ww[i];
 26             dfs(tt[i]);
 27         }
 28         i=pre[i];
 29     }
 30 }
 31 
 32 int lca(int x,int y)
 33 {
 34     if(deep[x]>deep[y])x^=y^=x^=y;
 35     int i;
 36     for(i=19;i>=0;i--)
 37     {
 38         if(deep[y]-deep[x]>=(1<<i))
 39         {
 40             y=s[y][i];
 41         }
 42     }
 43     if(x==y)return x;
 44     for(i=19;i>=0;i--)
 45     {
 46         if(s[x][i]!=s[y][i])
 47         {
 48             x=s[x][i];
 49             y=s[y][i];
 50         }
 51     }
 52     return fa[x];
 53 }
 54 void gao(int x)
 55 {
 56     int i=p[x];
 57     while (i)
 58     {
 59         if (tt[i]!=fa[x])
 60         {
 61             gao(tt[i]);
 62             sum[x]+=sum[tt[i]];
 63         }
 64         i=pre[i];
 65     }
 66 }
 67 int check(int x)
 68 {
 69     int cnt=0,dec=0;
 70     for (i=1;i<=n;i++)
 71     sum[i]=0;
 72     for (i=1;i<=m;i++)
 73     if (dist[i]>x)
 74     {
 75         cnt++;
 76         dec=max(dec,dist[i]-x);
 77         sum[A[i]]++;
 78         sum[B[i]]++;
 79         sum[LCA[i]]-=2;
 80     }
 81     gao(1);
 82     for (i=1;i<=n;i++)
 83     if ((sum[i]==cnt)&&(v[i]>=dec)) return 1;
 84     return 0;
 85 } 
 86 int main()
 87 {
 88     scanf("%d%d",&n,&m); 
 89     for (i=1;i<n;i++)
 90     {
 91         scanf("%d%d%d",&a,&b,&c);
 92         link(a,b,c);
 93         link(b,a,c);
 94     }
 95     dfs(1);
 96     for(i=1;i<=n;i++)s[i][0]=fa[i];
 97     for(int h=1;h<20;h++)
 98     {
 99         for(i=1;i<=n;i++)
100         {
101             s[i][h]=s[s[i][h-1]][h-1];
102         }
103     }
104     for (i=1;i<=m;i++)
105     {
106         scanf("%d%d",&A[i],&B[i]);
107         LCA[i]=lca(A[i],B[i]);
108         dist[i]=dis[A[i]]+dis[B[i]]-2*dis[LCA[i]];
109     }
110     int L=0,R=0;    
111     for (i=1;i<=m;i++)
112     R=max(R,dist[i]);
113     int mid;
114     while (L<=R)
115     {
116         mid=(L+R)>>1;
117         if (check(mid)) R=mid-1;else L=mid+1;
118     }
119     printf("%d
",L);
120 }