正題

---

題目大意

有一顆樹，求一條路徑長度k，要求$S\le k\le E$，求最小的k。

---

解題思路

其實對于每個點進行點分治，每次將整棵子樹的路徑加入平衡樹，然后在統計一次答案。時間復雜度$O(n^2)$。
之后我們發現其實每次就找該子樹的重心繼續，不用遍歷整棵子樹。時間復雜度$O(能過)$

---

code

#include<cstdio> #include<set> #include<algorithm> using namespace std; const int N=100100; struct node{int to,w,next; }a[N*3]; set<int> ga; int siz[N],ls[N],v[N],root,S,E,n,f[N],ans,tot,x,y,w; void addl(int x,int y,int w) {a[++tot].to=y;a[tot].w=w;a[tot].next=ls[x];ls[x]=tot; } void groot(int x,int fa)//尋找重心 {siz[x]=1;f[x]=0;for(int i=ls[x];i;i=a[i].next)if(a[i].to!=fa&&!v[a[i].to]){groot(a[i].to,x);siz[x]+=siz[a[i].to];f[x]=max(f[x],siz[a[i].to]);}f[x]=max(f[x],n-siz[x]);if (f[x]<f[root]) root=x; } void dfs(int x,int fa,int w,int flag)//點分治 {if(flag) ga.insert(w);else{if(S>=w&&w<=E) ans=min(ans,E);int maxs=*--ga.end();if (w+maxs>=S){int fnd=w+*ga.lower_bound(S-w);if (S<=fnd&&fnd<=E) ans=min(ans,fnd);}}for(int i=ls[x];i;i=a[i].next)if (!v[a[i].to]&&a[i].to!=fa)dfs(a[i].to,x,w+a[i].w,flag); } void dp(int x) {v[x]=1;ga.clear();ga.insert(0);for(int i=ls[x];i;i=a[i].next)if(!v[a[i].to]){dfs(a[i].to,x,a[i].w,0);//根到他的路徑加入平衡樹dfs(a[i].to,x,a[i].w,1);//統計答案}for(int i=ls[x];i;i=a[i].next)if(!v[a[i].to]){n=siz[a[i].to];root=0;groot(a[i].to,0);//尋找重心dp(root);//從重心繼續分治} } int main() {scanf("%d%d%d",&n,&S,&E);for(int i=1;i<n;i++){scanf("%d%d%d",&x,&y,&w);addl(x,y,w);addl(y,x,w);}ans=f[0]=2147483647;groot(1,0);dp(root);if(ans>E) ans=-1;printf("%d",ans); } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的nssl1248-B【点分治,平衡树】的全部內容，希望文章能夠幫你解決所遇到的問題。

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