題目描述

公元 \(2044\) 年，人類(lèi)進(jìn)入了宇宙紀(jì)元。

\(L\) 國(guó)有 \(n\) 個(gè)星球，還有 \(n-1\) 條雙向航道，每條航道建立在兩個(gè)星球之間，這 \(n-1\) 條航道連通了 \(L\) 國(guó)的所有星球。

小 \(P\) 掌管一家物流公司， 該公司有很多個(gè)運(yùn)輸計(jì)劃，每個(gè)運(yùn)輸計(jì)劃形如：有一艘物流飛船需要從 \(u_i\) 號(hào)星球沿最快的宇航路徑飛行到 $v_i$ 號(hào)星球去。顯然，飛船駛過(guò)一條航道是需要時(shí)間的，對(duì)于航道 $j$，任意飛船駛過(guò)它所花費(fèi)的時(shí)間為 $t_j$，并且任意兩艘飛船之間不會(huì)產(chǎn)生任何干擾。

為了鼓勵(lì)科技創(chuàng)新， $L$ 國(guó)國(guó)王同意小 $P$ 的物流公司參與 $L$ 國(guó)的航道建設(shè)，即允許小$P$ 把某一條航道改造成蟲(chóng)洞，飛船駛過(guò)蟲(chóng)洞不消耗時(shí)間。

在蟲(chóng)洞的建設(shè)完成前小 $P$ 的物流公司就預(yù)接了 $m$ 個(gè)運(yùn)輸計(jì)劃。在蟲(chóng)洞建設(shè)完成后，這 $m$ 個(gè)運(yùn)輸計(jì)劃會(huì)同時(shí)開(kāi)始，所有飛船一起出發(fā)。當(dāng)這 $m$ 個(gè)運(yùn)輸計(jì)劃都完成時(shí)，小 $P$ 的物流公司的階段性工作就完成了。

如果小 $P$ 可以自由選擇將哪一條航道改造成蟲(chóng)洞， 試求出小 $P$ 的物流公司完成階段性工作所需要的最短時(shí)間是多少？

輸入格式

第一行包括兩個(gè)正整數(shù) $n,m$，表示 L 國(guó)中星球的數(shù)量及小 P 公司預(yù)接的運(yùn)輸計(jì)劃的數(shù)量，星球從 $1$ 到 $n$ 編號(hào)。

接下來(lái) $n-1$ 行描述航道的建設(shè)情況，其中第 $i$ 行包含三個(gè)整數(shù) $a_i,b_i$ 和 $t_i$，表示第 $i$ 條雙向航道修建在 $a_i$ 與 $b_i$ 兩個(gè)星球之間，任意飛船駛過(guò)它所花費(fèi)的時(shí)間為 $t_i$。數(shù)據(jù)保證 $1 \leq a_i,b_i \leq n$且 $0 \leq t_i \leq 1000$。

接下來(lái) $m$ 行描述運(yùn)輸計(jì)劃的情況，其中第 $j$ 行包含兩個(gè)正整數(shù) $u_j$ 和$v_j$，表示第 $j$ 個(gè)運(yùn)輸計(jì)劃是從 $u_j$ 號(hào)星球飛往 $v_j$號(hào)星球。數(shù)據(jù)保證 $1 \leq u_i,v_i \leq n$

輸出格式

輸出文件只包含一個(gè)整數(shù)，表示小 $P$ 的物流公司完成階段性工作所需要的最短時(shí)間。

?

　　還記得當(dāng)初在$noip$考場(chǎng)上，不會(huì)樹(shù)剖不會(huì)二分答案，于是對(duì)于這道題就是狂跑lca啊lca……

　　后來(lái)學(xué)了各種東西之后，就自己打了一個(gè)復(fù)雜度為$O(n \log ^2 n)$的算法，大意如下：

　　先對(duì)于整棵樹(shù)進(jìn)行樹(shù)鏈剖分，然后考慮二分一個(gè)答案(因?yàn)轭}目所求是最大值最小，所以答案單調(diào))，只需判斷這個(gè)答案是否可行。于是我們需要把長(zhǎng)度大于$x$的路徑掃一遍，求一下這些路徑的交，從交中找出一條權(quán)值最大的邊，把這條邊權(quán)值變?yōu)?0$(顯然這樣最優(yōu)而且并不需要真的賦值為$0$)，判斷一下最長(zhǎng)路徑現(xiàn)在是否小于等于$x$即可。

　　接著，發(fā)現(xiàn)被卡了。在UOJ上只有97分。于是，接下來(lái)就是奇技淫巧時(shí)間。

　　有一次有點(diǎn)無(wú)聊，于是把樹(shù)鏈剖分中的求重兒子部分的代碼中的小于號(hào)改為了小于等于號(hào)，就這么AC了……汗……

　　下面是代碼：

#include<iostream> #include<cstdio> #include<cstring> #define INF 2147483647 #define maxn 300001using namespace std;struct data{int f,t,v; }he[maxn]; int fa[maxn],head[maxn*2],to[maxn*2],next[maxn*2],c[maxn*2]; int dep[maxn],son[maxn],top[maxn],siz[maxn],w[maxn],zui; int tc[maxn],fc1[maxn],fc[maxn],cha[maxn+1],tt,m,n,x,y,l,r;int getint(){int w=0,q=0;char c=getchar();while((c>'9'||c<'0')&&c!='-') c=getchar();if(c=='-') q=1,c=getchar();while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();return q?-w:w; }void dfs1(int u,int dd){dep[u]=dd;siz[u]++;for(int i=head[u];i;i=next[i])if(!dep[to[i]]){dfs1(to[i],dd+1);siz[u]+=siz[to[i]];fa[to[i]]=u;fc[to[i]]=c[i];if(siz[to[i]]>=siz[son[u]]) son[u]=to[i];} }void dfs2(int u,int dd){w[u]=++tt;top[u]=dd;fc1[tt]=fc[u];if(son[u]) tc[son[u]]=tc[u]+fc[son[u]],dfs2(son[u],dd);for(int i=head[u];i;i=next[i])if(to[i]!=son[u]&&to[i]!=fa[u])dfs2(to[i],to[i]); }inline int lca(int x,int y){int ju=0;while(top[x]!=top[y]){int a=fa[top[x]],b=fa[top[y]];if(dep[a]<dep[b]) swap(x,y),swap(a,b);cha[w[x]+1]--;cha[w[top[x]]]++;ju+=tc[x]+fc[top[x]];x=a;}if(dep[x]<dep[y]) swap(x,y);cha[w[x]+1]--;cha[w[son[y]]]++;ju+=tc[x]-tc[y];return ju; }inline bool pd(int kk){int ci=0;memset(cha,0,sizeof(cha));for(register int i=1;i<=m;i++)if(he[i].v>kk) lca(he[i].f,he[i].t),ci++;int hehe=0,hh=c[0];for(register int i=1;i<=tt;i++){hh+=cha[i];if(hh==ci) hehe=max(hehe,fc1[i]);}if(zui-hehe<=kk) return 1;return 0; }int main(){n=getint();m=getint();for(int i=1;i<n;i++){x=getint();y=getint();to[++tt]=y,next[tt]=head[x],head[x]=tt;to[++tt]=x,next[tt]=head[y],head[y]=tt;c[tt-1]=c[tt]=getint();}dfs1(1,1);tt=0;dfs2(1,1);for(int i=1;i<=m;i++){he[i].f=getint();he[i].t=getint();he[i].v=lca(he[i].f,he[i].t);r=max(r,he[i].v);}zui=r++;while(l!=r){int mid=(l+r)>>1;if(pd(mid))r=mid;else l=mid+1;}printf("%d",l);return 0; }

　　但是后來(lái)，我發(fā)現(xiàn)其實(shí)這個(gè)算法是可以優(yōu)化到$O(n \log n)$的。設(shè)當(dāng)前二分的答案為$x$，由于每一次最長(zhǎng)路徑長(zhǎng)度小于等于$x$時(shí)顯然可以，否則不滿足的所有路徑的交必定在最長(zhǎng)路徑上(交為空時(shí)其實(shí)也是最長(zhǎng)路徑的子集)，而且是連續(xù)的一段。然后我們把最長(zhǎng)鏈摳出來(lái)，對(duì)于其他每一條路徑與最長(zhǎng)路徑求一下交，那么路徑的交就變成區(qū)間上的問(wèn)題了，可以線性地做。于是復(fù)雜度降為$O(n \log n)$。

　　還有怎么兩條路徑求交的問(wèn)題。由于我們只需求出兩條路徑交的兩個(gè)端點(diǎn)，可以把這兩條路徑的共4個(gè)點(diǎn)lca一下，分類(lèi)討論即可。

　　下面貼代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define maxn 300010using namespace std; typedef long long llg;struct data{int u,v,g,x; }s[maxn]; int n,m,dep[maxn],son[maxn],siz[maxn],fa[maxn],tc[maxn],top[maxn],fc[maxn]; int head[maxn],to[maxn<<1],next[maxn<<1],c[maxn<<1],tt,K,nn,now; int dc[maxn],cd[maxn],ld,b[maxn],lb,bb[maxn],ca[maxn];int getint(){int w=0;bool q=0;char c=getchar();while((c>'9'||c<'0')&&c!='-') c=getchar();if(c=='-') c=getchar(),q=1;while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();return q?-w:w; }void link(int x,int y){to[++tt]=y;next[tt]=head[x];head[x]=tt;to[++tt]=x,next[tt]=head[y];head[y]=tt;c[tt]=c[tt-1]=getint(); }void dfs(int u){siz[u]=1;for(int i=head[u],v;v=to[i],i;i=next[i])if(!siz[v]){dep[v]=dep[u]+1; fa[v]=u; fc[v]=c[i];dfs(v); siz[u]+=siz[v];if(siz[v]>siz[son[u]]) son[u]=v;} }void dfs(int u,int d){top[u]=d;if(son[u]) tc[son[u]]=tc[u]+fc[son[u]],dfs(son[u],d);for(int i=head[u],v;v=to[i],i;i=next[i])if(!top[v]) dfs(v,v); }inline int lca(int u,int v){//樹(shù)鏈剖分求lcanow=0;while(top[u]!=top[v]){if(dep[fa[top[u]]]<dep[fa[top[v]]]) swap(u,v);now+=tc[u]+fc[top[u]]; u=fa[top[u]];}if(dep[u]>dep[v]) swap(u,v);now+=tc[v]-tc[u]; return u; }void kou(int u,int v,int g){//把最長(zhǎng)路徑摳出來(lái)while(u!=g) cd[++ld]=u,ca[ld]=fc[u],u=fa[u]; cd[++ld]=g; //從u到g的路徑while(v!=g) b[++lb]=v,bb[lb]=fc[v],v=fa[v]; //從v到g的路徑while(lb) ca[ld]=fc[b[lb]],cd[++ld]=b[lb--]; //ca表示長(zhǎng)度f(wàn)or(int i=1;i<=ld;i++) dc[cd[i]]=i; }inline bool pd(int x){//判斷是否可行int l=1,r=ld,gi=0;for(register int i=1;i<=m;i++)if(s[i].x>x){l=max(l,s[i].u);r=min(r,s[i].v);}for(int i=l;i<r;i++) gi=max(gi,ca[i]);return nn-gi<=x; }inline void gi(int &xx,int u){int x,y;x=lca(u,s[K].u); if(dep[x]>dep[s[K].g]){xx=dc[x];return;}y=lca(u,s[K].v); if(dep[y]>dep[s[K].g]){xx=dc[y];return;}xx=dc[s[K].g];//點(diǎn)在路徑之外,要么另一個(gè)點(diǎn)的兩個(gè)lca在最長(zhǎng)路徑上,此時(shí)視為最長(zhǎng)路徑的最上點(diǎn),要么兩條路徑交為空 }int main(){n=getint(); m=getint();for(int i=1;i<n;i++) link(getint(),getint());dep[1]=1;dfs(1); dfs(1,1);for(register int i=1;i<=m;i++){s[i].u=getint(); s[i].v=getint();s[i].g=lca(s[i].u,s[i].v); s[i].x=now;if(now>nn) nn=now,K=i;//nn為最長(zhǎng)路徑長(zhǎng)度,K為最長(zhǎng)路徑標(biāo)號(hào)}kou(s[K].u,s[K].v,s[K].g);for(register int i=1,l,r;i<=m;i++)if(i!=K){gi(l,s[i].u); gi(r,s[i].v);//lca分類(lèi)討論求路徑交if(l>r) swap(l,r);s[i].u=l,s[i].v=r;//注意這里的區(qū)間為[l,r)}s[K].u=1,s[K].v=ld;int l=0,r=nn,mid;while(l!=r){mid=l+r>>1;if(pd(mid)) r=mid;else l=mid+1;}printf("%d",l); }

　　又或者可以直接優(yōu)化查分，使得差分變?yōu)?O(1)$，具體思路如下：把一條路徑上的邊全部加$1$，那么可以把兩個(gè)端點(diǎn)的值加$1$，lca的值減$2$，全部完成后dfs一遍解決。但不知道為什么，速度比第一種算法還要慢，大概是常數(shù)有點(diǎn)大吧……

　　下面貼代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define maxn 300010using namespace std; typedef long long llg;struct data{int u,v,g,x; }s[maxn]; int n,m,dep[maxn],son[maxn],siz[maxn],fa[maxn],tc[maxn],top[maxn],fc[maxn]; int head[maxn],to[maxn<<1],next[maxn<<1],c[maxn<<1],tt,now,nn; int ch[maxn],ci,_m;int getint(){int w=0;bool q=0;char c=getchar();while((c>'9'||c<'0')&&c!='-') c=getchar();if(c=='-') c=getchar(),q=1;while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();return q?-w:w; }void link(int x,int y){to[++tt]=y;next[tt]=head[x];head[x]=tt;to[++tt]=x,next[tt]=head[y];head[y]=tt;c[tt]=c[tt-1]=getint(); }void dfs(int u){siz[u]=1;for(int i=head[u],v;v=to[i],i;i=next[i])if(!siz[v]){dep[v]=dep[u]+1; fa[v]=u; fc[v]=c[i];dfs(v); siz[u]+=siz[v];if(siz[v]>siz[son[u]]) son[u]=v;} }void dfs(int u,int d){top[u]=d;if(son[u]) tc[son[u]]=tc[u]+fc[son[u]],dfs(son[u],d);for(int i=head[u],v;v=to[i],i;i=next[i])if(!top[v]) dfs(v,v); }int lca(int u,int v){now=0;while(top[u]!=top[v]){if(dep[fa[top[u]]]<dep[fa[top[v]]]) swap(u,v);now+=tc[u]+fc[top[u]]; u=fa[top[u]];}if(dep[u]>dep[v]) swap(u,v);now+=tc[v]-tc[u]; return u; }void work(int u){for(int i=head[u],v;v=to[i],i;i=next[i])if(v!=fa[u])work(v),ch[u]+=ch[v],ch[v]=0;if(ch[u]==ci) _m=max(_m,fc[u]); }bool pd(int x){ci=_m=ch[1]=0;for(int i=1;i<=m;i++)if(s[i].x>x){ch[s[i].u]++;ch[s[i].v]++;ch[s[i].g]-=2; ci++;}work(1);return nn-_m<=x; }int main(){File("a");n=getint(); m=getint();for(int i=1;i<n;i++) link(getint(),getint());dep[1]=1;dfs(1); dfs(1,1);for(int i=1;i<=m;i++){s[i].u=getint(); s[i].v=getint();s[i].g=lca(s[i].u,s[i].v);nn=max(nn,s[i].x=now);}int l=0,r=nn,mid;while(l!=r){mid=l+r>>1;if(pd(mid)) r=mid;else l=mid+1;}printf("%d",l); }

　　不過(guò)這道題的標(biāo)解的復(fù)雜度好像是并查集復(fù)雜度……留坑待填……

轉(zhuǎn)載于:https://www.cnblogs.com/lcf-2000/p/5861051.html

總結(jié)

以上是生活随笔為你收集整理的UOJ #150 【NOIP2015】 运输计划的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。