[NOIp2015] 运输计划

NOIp 2015 D2T3。

洛谷 P2680 传送门

vijos 1983 传送门（vijos交题的人少，不用等）

题里所求的实际上是删掉一条边后所有路径中的最大值。

我们很难直接求出这个最大值的最小值，但是如果给定一个值，可以验证是否合法。

使这个最大值最小，考虑倍增答案。

先求出每个运输计划的长度，倍增答案。

check的时候，数出所有总长大于k的运输计划，显然它们都需要删边使长度降到k以下。

再利用树上差分，统计树上每条边分别被上述那些运输计划经过了多少次。

如果能找到一条边被所有的运输计划经过，而且最长的运输计划减去那条边之后，长度能够降到k以下，则这个k合法。

最后倍增出不合法的最大值，加一即为合法的最小值。

注意到当合法的最小值为0的时候，不合法的最大值为-1。

而我们无法倍增出-1。

所以最后特判一下这种情况即可。

LCA用树剖，防止被卡常。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int n,m,mx,ex,ans;
 7 int hd[300005],nx[600005],to[600005],len[600005],ec;
 8 int dis[300005],dep[300005],sz[300005],f[300005],up[300005];
 9 int tp[300005],son[300005],pos[300005],pc;
10 
11 void edge(int af,int at,int vt)
12 {
13     to[++ec]=at;
14     len[ec]=vt;
15     nx[ec]=hd[af];
16     hd[af]=ec;
17 }
18 
19 void dfs(int p,int fa,int el)
20 {
21     dis[p]=dis[fa]+el,dep[p]=dep[fa]+1;
22     f[p]=fa,sz[p]=1,pos[++pc]=p,up[p]=el;
23     for(int i=hd[p];i;i=nx[i])
24     {
25         if(to[i]==fa)continue;
26         dfs(to[i],p,len[i]);
27         sz[p]+=sz[to[i]];
28         if(sz[to[i]]>sz[son[p]])son[p]=to[i];
29     }
30 }
31 
32 void findtp(int p)
33 {
34     if(p==son[f[p]])tp[p]=tp[f[p]];
35     else tp[p]=p;
36     for(int i=hd[p];i;i=nx[i])
37         if(to[i]!=f[p])findtp(to[i]);
38 }
39 
40 int lca(int x,int y)
41 {
42     while(tp[x]!=tp[y])dep[tp[x]]>dep[tp[y]]?x=f[tp[x]]:y=f[tp[y]];
43     return dep[x]<dep[y]?x:y;
44 }
45 
46 int h[300005],a[300005],b[300005],l[300005],d[300005];
47 
48 int check(int k)
49 {
50     if(k>=mx)return 1;
51     if(k<mx-ex)return 0;
52     memset(h,0,sizeof(h));
53     int cnt=0;
54     for(int i=1;i<=m;i++)
55     {
56         if(d[i]>k)
57         {
58             cnt++;
59             h[a[i]]++,h[b[i]]++;
60             h[l[i]]-=2;
61         }
62     }
63     for(int i=n;i;i--)
64     {
65         h[f[pos[i]]]+=h[pos[i]];
66         if(mx-up[pos[i]]<=k&&cnt==h[pos[i]])return 1;
67     }
68     return 0;
69 }
70 
71 int main()
72 {
73     scanf("%d%d",&n,&m);
74     for(int i=1;i<n;i++)
75     {
76         int ff,tt,vv;
77         scanf("%d%d%d",&ff,&tt,&vv);
78         edge(ff,tt,vv);
79         edge(tt,ff,vv);
80         ex=max(ex,vv);
81     }
82     dfs(1,1,0);
83     findtp(1);
84     for(int i=1;i<=m;i++)
85     {
86         scanf("%d%d",&a[i],&b[i]);
87         l[i]=lca(a[i],b[i]);
88         d[i]=dis[a[i]]+dis[b[i]]-(dis[l[i]]<<1);
89         mx=max(mx,d[i]);
90     }
91     for(int i=30;i>=0;i--)
92         if(!check(ans|(1<<i)))ans|=(1<<i);
93     if(!ans)ans-=check(0);
94     printf("%d",ans+1);
95     return 0;
96 }