題目鏈接：點這里

Solution:

點分治，算出點對之間的距離，記錄所屬子樹和與跟之間的邊數。

對于每個點，記錄排序過后位置離自己最近的不同子樹的點，記做go[x]

每次二分去更新，若遇到同一子樹的點，則嘗試用go[x]去更新

排序以距離為第一關鍵字，邊數為第二關鍵字(這樣二分出來的點一定是滿足條件的最優的點)

詳見代碼(注意編號從0開始)

Code:

#include<bits/stdc++.h> #define ll long long #define inf 2147483647 using namespace std; const int N=2e5+1; int n,k,rt,szt,cnt,tot,head[N]; int ans,sz[N],mx[N],vis[N],go[N]; struct Edge{int nxt,to,val;}edge[N<<1]; struct Pos{int dis,be,u;}p[N]; inline bool cmp(Pos a,Pos b){return a.dis==b.dis?a.u<b.u:a.dis<b.dis;} void ins(int x,int y,int z){edge[++cnt].nxt=head[x];edge[cnt].to=y;edge[cnt].val=z;head[x]=cnt; } void getrt(int x,int fa){mx[x]=0;sz[x]=1;for(int i=head[x];~i;i=edge[i].nxt){int y=edge[i].to;if(vis[y]||y==fa) continue;getrt(y,x);sz[x]+=sz[y];mx[x]=max(mx[x],sz[y]);}mx[x]=max(mx[x],szt-sz[x]);if(mx[x]<mx[rt]) rt=x; } void getdis(int x,int fa,int d,int s,int num){p[++tot].dis=d;p[tot].be=s;p[tot].u=num;for(int i=head[x];~i;i=edge[i].nxt){int y=edge[i].to;if(vis[y]||y==fa) continue;getdis(y,x,d+edge[i].val,s,num+1);} } int find(int x,int l,int r){while(l<r){int mid=(l+r)>>1;if(x+p[mid].dis<k) l=mid+1;else r=mid;}return l; } void divide(int x){vis[x]=1;tot=0;for(int i=head[x];~i;i=edge[i].nxt){int y=edge[i].to;if(vis[y]) continue;getdis(y,x,edge[i].val,y,1);}sort(p+1,p+tot+1,cmp);for(int i=1;i<=tot;i++)if(p[i].dis==k) ans=min(ans,p[i].u);for(int i=tot;i>=1;i--){if(p[i].be!=p[i+1].be) go[i]=i+1;else go[i]=go[i+1];}p[tot+1].dis=0;for(int i=1;i<=tot;i++){int x=find(p[i].dis,i+1,tot);if(p[i].dis+p[x].dis==k){if(p[i].be!=p[x].be) ans=min(ans,p[i].u+p[x].u);else if(p[i].dis+p[go[x]].dis==k) ans=min(ans,p[i].u+p[go[x]].u);}}for(int i=head[x];~i;i=edge[i].nxt){int y=edge[i].to;if(vis[y]) continue;rt=2e5;szt=sz[y];getrt(y,x);divide(rt);} } int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f; } int main(){n=read(),k=read();memset(head,-1,sizeof(head));for(int i=1;i<n;i++){int x=read(),y=read(),z=read();ins(x,y,z);ins(y,x,z);}rt=2e5;szt=n;mx[rt]=inf;getrt(0,-1);ans=inf;divide(rt);printf("%d\n",ans==inf?-1:ans);return 0; }

轉載于:https://www.cnblogs.com/NLDQY/p/10824460.html

總結

以上是生活随笔為你收集整理的[IOI2011]Race的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。