正題

---

題目大意

求一棵樹上有多少條路徑長(zhǎng)度$\le len$

---

解題思路

首先普通點(diǎn)分治。掃描的時(shí)候?qū)⒚總€(gè)點(diǎn)保存為一個(gè)二元組$(dis,gra)$分別表示離(分治到的)根的距離，屬于根的那顆子樹。

然后按照$dis$排序，兩個(gè)指針$L,R$用$c{n}_i$表示$[L+1,R]$這個(gè)區(qū)間內(nèi)是$i$這個(gè)子樹的點(diǎn)的個(gè)數(shù)。

然后我們發(fā)現(xiàn)滿足$di{s}_L+di{s}_R\le len$這個(gè)范圍根據(jù)$L$的向前$R$是單調(diào)不升的然后兩個(gè)指針維護(hù)一下每次統(tǒng)計(jì)一下答案$R?L?c{n}_L$

---

$code$

#include<cstdio> #include<set> #include<algorithm> using namespace std; const int N=100100; struct node{int to,w,next; }a[N*3]; struct Num_node{int a,b; }num[N]; int siz[N],ls[N],v[N],root,len,n,f[N],ans,tot,x,y,w,cnt,cn[N]; bool cmp(Num_node x,Num_node y) {return x.a<y.a;} 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 grafa) {num[++cnt].b=grafa;num[cnt].a=w;cn[grafa]++;for(int i=ls[x];i;i=a[i].next)if (!v[a[i].to]&&a[i].to!=fa)cn[a[i].to]=0,dfs(a[i].to,x,w+a[i].w,grafa); } void dp(int x) {v[x]=1;cnt=0;for(int i=ls[x];i;i=a[i].next)if(!v[a[i].to])dfs(a[i].to,x,a[i].w,a[i].to);sort(num+1,num+1+cnt,cmp);for(int L=0,R=cnt;L<=R;L++,cn[num[L].b]--){while(num[L].a+num[R].a>len) cn[num[R].b]--,R--;if(L>=R) break;ans+=(R-L-cn[num[L].b]);}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",&n,&len);for(int i=1;i<n;i++){scanf("%d%d%d",&x,&y,&w);addl(x,y,w);addl(y,x,w);}f[0]=2147483647;groot(1,0);dp(root);printf("%d",ans); }

總結(jié)

以上是生活随笔為你收集整理的jzoj1166-树中点对距离【点分治】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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