題目描述
給定一棵N(1<=N<=100000)個(gè)結(jié)點(diǎn)的帶權(quán)樹，每條邊都有一個(gè)權(quán)值（為正整數(shù)，小于等于1001）。定義dis(u,v)為u,v兩點(diǎn)間的最短路徑長(zhǎng)度，路徑的長(zhǎng)度定義為路徑上所有邊的權(quán)和。再給定一個(gè)K(1<=K<=10^9)，如果對(duì)于不同的兩個(gè)結(jié)點(diǎn)u,v，如果滿足dist(u,v)<=K，則稱(u,v)為合法點(diǎn)對(duì)。求合法點(diǎn)對(duì)個(gè)數(shù)。
題目大意
求樹中距離小于k的點(diǎn)對(duì)個(gè)數(shù)
數(shù)據(jù)范圍
對(duì)于50%的數(shù)據(jù),n<=1000,k<=1000; 對(duì)于100%的數(shù)據(jù),n<=100000,k<=10^9;
樣例輸入
5 4 1 2 3 1 3 1 1 4 2 3 5 1
樣例輸出
8
解題思路
不寫了233
代碼
#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#include <ctime>#define Maxn 100005using namespace std;inline int Getint(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}int fa[Maxn],h[Maxn],size[Maxn],dep[Maxn];bool vis[Maxn];int n,k,cnt=0,L,r,Min;struct node{int to,next,v;}e[Maxn*2];void AddEdge(int x,int y,int v){e[++cnt]=(node){y,h[x],v};h[x]=cnt;}void Init(){ n=Getint(),k=Getint(); for(int i=1;i<n;i++){ int x,y,v; x=Getint(),y=Getint(),v=Getint(); fa[y]=x; AddEdge(x,y,v); AddEdge(y,x,v); } memset(vis,0,sizeof(vis));}int dfssize(int u,int PRe){ size[u]=1; for(int p=h[u];p;p=e[p].next){ int y=e[p].to; if(vis[y]||y==pre)continue; size[u]+=dfssize(y,u); } return size[u];}void Getroot(int u,int pre,int tot,int &root){ int Max=tot-size[u]; for(int p=h[u];p;p=e[p].next){ int y=e[p].to; if(vis[y]||y==pre)continue; Getroot(y,u,tot,root); Max=max(Max,size[y]); } if(Max<Min){ Min=Max; root=u; }}void Getlen(int u,int pre,int d){ dep[r++]=d; for(int p=h[u];p;p=e[p].next){ int y=e[p].to; if(vis[y]||y==pre)continue; Getlen(y,u,d+e[p].v); }}int Calc(int L,int r){ sort(dep+L,dep+r); int ret=0,Pos=r-1; for(int i=L;i<r;i++){ if(dep[i]>k)break; while(Pos>=L&&dep[i]+dep[Pos]>k)Pos--; ret+=Pos-L+1; if(Pos>i)ret--; } return ret/2;}int Solve(int u){ int tot=dfssize(u,0),ret=0,root; Min=0x7fffffff; Getroot(u,0,tot,root); vis[root]=true; for(int p=h[root];p;p=e[p].next){ int y=e[p].to; if(vis[y])continue; ret+=Solve(y); } L=r=0; for(int p=h[root];p;p=e[p].next){ int y=e[p].to; if(vis[y])continue; Getlen(y,root,e[p].v); ret-=Calc(L,r); L=r; } ret+=Calc(0,r); for(int i=0;i<r;i++) if(dep[i]<=k)ret++; else break; vis[root]=false; return ret;}int main(){ Init(); cout<<Solve(1)<<"/n";}
