[NOIP2015提高組]運輸計劃

題目：BZOJ4326、洛谷P2680、Vijos P1983、UOJ#150、codevs4632、codevs5440。

題目大意：有一棵帶權樹，有一些運輸計劃，第i個運輸計劃從ai到bi，耗時為ai到bi的距離，所有運輸計劃一起開始。現在可以把一條邊權變成0，求最終運輸計劃最短要多少時間。

解題思路：標算是樹剖，然而我并不會……

我的方法是LCA+二分+樹上差分。

首先LCA，求出每個運輸計劃的長度，可一遍dfs求出每個節點到根的距離dist，則a到b的長度為dist[a]+dist[b]-(dist[lca(a,b)]<<1)。

接著二分答案，然后判斷答案可行性。

對于每一個答案，我們要找的是所有長度大于當前答案的運輸計劃的公共邊，因為只有所有長度大于當前答案的運輸計劃全部變成小于等于當前答案，當前答案才可行。

用樹上差分（不懂請百度）。我們用s[i]記錄i到它父親這條邊有多少計劃經過。

對于每個運輸計劃，如果長度大于當前答案，我們給s[a]+1,s[b]+1,s[lca(a,b)]-2，因為我們要統計的是邊，所以對于兩個點，lca(a,b)對應的邊實際是沒有走到的，所以-2。

差分完后判斷答案可行性即可。

我用倍增時間復雜度為$O(m\log_2 n+(n+m)\log_2 len)$，len為運輸計劃的最大長度。

但常數巨大，1s很容易被卡，因此有些地方還過不掉。例如我在UOJ上就被卡97。但在時限較寬或數據較弱的地方還是能AC的。

C++ Code：

%:pragma GCC optimize(2)
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
char buf[10700005];
int bufpos,n,m,head[300001],deep[300001],p[300001][21],dist[300001],s[300001],fa_edge[300001],mx,now;
struct edge{int to,dis,nxt;
}e[600003];
struct que{int a,b,len,LCA;
}f[300001];
inline int max(int a,int b){return(a>b)?a:b;}
inline int readint(){char c=buf[bufpos++];for(;!isdigit(c);c=buf[bufpos++]);int p=0;for(;isdigit(c);c=buf[bufpos++])p=(p<<3)+(p<<1)+(c^'0');return p;
}
void dfs(int s){for(int i=head[s];i;i=e[i].nxt)if(!deep[e[i].to]){fa_edge[e[i].to]=i;deep[e[i].to]=deep[s]+1;p[e[i].to][0]=s;dist[e[i].to]=dist[s]+e[i].dis;dfs(e[i].to);}
}
int lca(int x,int y){if(deep[x]<deep[y])x^=y^=x^=y;int i;for(i=0;(1<<i)<=deep[x];++i);--i;for(int j=i;j>-1;--j)if(deep[p[x][j]]>=deep[y])x=p[x][j];if(x==y)return x;for(int j=i;j>-1;--j)if(p[x][j]!=-1&&p[x][j]!=p[y][j])x=p[x][j],y=p[y][j];return p[x][0];
}
void updata(int now){for(int i=head[now];i;i=e[i].nxt)if(deep[now]<deep[e[i].to]){updata(e[i].to);s[now]+=s[e[i].to];}
}
bool ok(int ans){memset(s,0,sizeof s);int gz=0;for(int i=1;i<=n;++i)if(f[i].len>ans){++gz;++s[f[i].a];++s[f[i].b];s[f[i].LCA]-=2;}updata(1);for(int i=1;i<=m;++i)if(s[i]==gz&&mx-ans<=e[fa_edge[i]].dis)return true;return false;
}
int main(){buf[fread(buf,1,10700000,stdin)]=bufpos=0;m=readint(),n=readint();for(int i=1;i<m;++i){int from=readint(),to=readint(),dis=readint();now=i<<1;e[now-1]=(edge){to,dis,head[from]};head[from]=now-1;e[now]=(edge){from,dis,head[to]};head[to]=now;}memset(p,-1,sizeof p);dist[1]=0;deep[1]=1;dfs(1);for(int j=1;(1<<j)<=m;++j)for(int i=1;i<=m;++i)if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1];int l=0,r=0,mid;for(int i=1;i<=n;++i){f[i].a=readint();f[i].b=readint();f[i].LCA=lca(f[i].a,f[i].b);r=max(r,f[i].len=dist[f[i].a]+dist[f[i].b]-(dist[f[i].LCA]<<1));}mx=r;++r;while(l<r){mid=l+r>>1;if(ok(mid))r=mid;elsel=mid+1;}printf("%d\n",r);return 0;
}

倍增時間復雜度比較高，我改成用Tarjan求LCA，速度瞬間變快，在UOJ上成功卡了過去。不過codevs4632仍然被卡。

以下為Tarjan代碼。

C++ Code：

%:pragma GCC optimize(2)
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
char buf[10700005];
int bufpos,n,m,head[300001],deep[300001],dist[300001],s[300001],fa_edge[300001],mx,now,headq[300001],nq=0;
bool vis[300001];
int fa[300001];
struct edge{int to,dis,nxt;
}e[600003];
struct que{int a,b,len,LCA;
}f[300001];
struct Query{int same,nxt,to,num;bool flag;
}q[600003];
int find(int x){return(fa[x]==x)?x:(fa[x]=find(fa[x]));}
inline int max(int a,int b){return(a>b)?a:b;}
inline int readint(){char c=buf[bufpos++];for(;!isdigit(c);c=buf[bufpos++]);int p=0;for(;isdigit(c);c=buf[bufpos++])p=(p<<3)+(p<<1)+(c^'0');return p;
}
void dfs(int s){for(int i=head[s];i;i=e[i].nxt)if(!deep[e[i].to]){fa_edge[e[i].to]=i;deep[e[i].to]=deep[s]+1;dist[e[i].to]=dist[s]+e[i].dis;dfs(e[i].to);}
}
void tarjan(int root){for(int i=head[root];i;i=e[i].nxt)if(deep[root]<deep[e[i].to]){tarjan(e[i].to);fa[e[i].to]=root;vis[e[i].to]=true;}for(int i=headq[root];i;i=q[i].nxt)if(vis[q[i].to]&&!q[i].flag){q[i].flag=q[q[i].same].flag=true;f[q[i].num].LCA=find(q[i].to);}
}
void updata(int now){for(int i=head[now];i;i=e[i].nxt)if(deep[now]<deep[e[i].to]){updata(e[i].to);s[now]+=s[e[i].to];}
}
bool ok(int ans){memset(s,0,sizeof s);int gz=0;for(int i=1;i<=n;++i)if(f[i].len>ans){++gz;++s[f[i].a];++s[f[i].b];s[f[i].LCA]-=2;}updata(1);for(int i=1;i<=m;++i)if(s[i]==gz&&mx-ans<=e[fa_edge[i]].dis)return true;return false;
}
int main(){buf[fread(buf,1,10700000,stdin)]=bufpos=0;m=readint(),n=readint();for(int i=1;i<m;++i){int from=readint(),to=readint(),dis=readint();now=i<<1;e[now-1]=(edge){to,dis,head[from]};head[from]=now-1;e[now]=(edge){from,dis,head[to]};head[to]=now;fa[i]=i;}fa[m]=m;deep[1]=1;dfs(1);int l=0,r=0,mid;for(int i=1;i<=n;++i){f[i].a=readint();f[i].b=readint();int& x=f[i].a,&y=f[i].b;q[++nq].to=y;q[nq].same=nq+1;q[nq].num=i;q[nq].nxt=headq[x];headq[x]=nq;q[++nq].to=x;q[nq].same=nq-1;q[nq].num=i;q[nq].nxt=headq[y];headq[y]=nq;if(x==y)q[nq].flag=q[nq-1].flag=true,f[i].LCA=x;}tarjan(1);for(int i=1;i<=n;++i)r=max(r,f[i].len=dist[f[i].a]+dist[f[i].b]-(dist[f[i].LCA]<<1));mx=r;++r;while(l<r){mid=l+r>>1;if(ok(mid))r=mid;elsel=mid+1;}printf("%d\n",r);return 0;
}

?