点分治第一题
这题我们考虑点分治
首先我们需要找到树的重心
然后做一遍
然后分成左右两块继续做，每一块重复上面的操作
具体的，我们每次计算每个点到重心的距离
然后放到一个数组里，再将距离和小于k的算进去
但是有可能重复统计了子树里面的数值
所以点分治的时候再减一下就好了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>using namespace std;int n,k,h[10005],en,mx[10005],siz[10005],ans,root,val,vis[10005],temp[10005],cnt;struct Edge{int b,v,next;}e[20005];void AddEdge(int sa,int sb,int sc){e[++en].b=sb;e[en].v=sc;e[en].next=h[sa];h[sa]=en;}void DfsSiz(int u,int fa){siz[u]=1;mx[u]=0;for(int i=h[u];i;i=e[i].next){ int v=e[i].b; if(v!=fa && !vis[v]){ DfsSiz(v,u); siz[u]+=siz[v]; mx[u]=max(mx[u],siz[v]); }}}void DfsRoot(int point,int u,int fa){mx[u]=max(mx[u],siz[point]-siz[u]);if(val>mx[u]){val=mx[u];root=u;}for(int i=h[u];i;i=e[i].next){ int v=e[i].b; if(v!=fa && !vis[v])DfsRoot(point,v,u);}}void GetDist(int u,int fa,int val){temp[++cnt]=val;for(int i=h[u];i;i=e[i].next){ int v=e[i].b; if(v!=fa && !vis[v])GetDist(v,u,val+e[i].v);}}int Cal(int u,int val){cnt=0;int now=0;GetDist(u,u,val);sort(temp+1,temp+cnt+1);int i=1,j=cnt;while(i<j){ while(temp[i]+temp[j]>k && i<j)j--; now+=j-i; i++;}return now;}void Dfs(int u){val=2100000000;DfsSiz(u,u);DfsRoot(u,u,0);ans+=Cal(root,0);vis[root]=1;for(int i=h[root];i;i=e[i].next){ int v=e[i].b; if(!vis[v]){ ans-=Cal(v,e[i].v); Dfs(v); }}}int main(){freopen("1741.in","r",stdin);freopen("1741.out","w",stdout);while(scanf("%d %d",&n,&k),n|k){ memset(h,0,sizeof(h)); memset(vis,0,sizeof(vis)); ans=en=0; for(int i=1;i<n;i++){ int sa,sb,sc; scanf("%d %d %d",&sa,&sb,&sc); AddEdge(sa,sb,sc); AddEdge(sb,sa,sc); } Dfs(1); printf("%d\n",ans);}return 0;} |
