1468: Tree
Description
给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K
Input
N（n<=40000） 接下来n-1行边描述管道，按照题目中写的输入 接下来是k
Output
一行，有多少对点之间的距离小于等于k
Sample Input
7
1 6 13
6 3 9
3 5 7
4 1 3
2 4 20
4 7 2
10
1 6 13
6 3 9
3 5 7
4 1 3
2 4 20
4 7 2
10
Sample Output
5
这是一道萌萌哒的点分治。。。
推荐一份材料。。。
漆子超犇的《分治算法在树的路径问题中的应用》
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 97 98 99 100 | #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int N,K,tot,Q,Num;int first[40010];int next[80010];int end[80010];int value[80010];int mark[40010];int size[40010];int maxx[40010];int Dist[40010];int Belong[40010];int P[40010];int Focus;struct Pair{ int st,nd; Pair(int a=0,int b=0){ st=a; nd=b; }}A[40010];int cmp(const Pair &x,const Pair &y){ return x.st<y.st;}void Add(int x,int y,int z){ next[++tot]=first[x]; first[x]=tot; end[tot]=y; value[tot]=z; next[++tot]=first[y]; first[y]=tot; end[tot]=x; value[tot]=z;}void Search(int x,int fa,int m){ maxx[x]=m-size[x]; for (int k=first[x],v;v=end[k],k;k=next[k]){ if (v==fa) continue; if (mark[v]) continue; Search(v,x,m); maxx[x]=max(maxx[x],size[v]); } if ((maxx[x]<maxx[Focus])||(!Focus)) Focus=x;}void Dfs(int x,int fa){ size[x]=1; for (int k=first[x],v;v=end[k],k;k=next[k]){ if (v==fa) continue; if (mark[v]) continue; Dist[v]=Dist[x]+value[k]; Belong[v]=Belong[x]; P[Belong[v]]++; A[++Num]=Pair(Dist[v],Belong[v]); Dfs(v,x); size[x]+=size[v]; }}int QAns(int x){ mark[x]=1; Num=0; P[x]=1; A[++Num]=Pair(0,x); for (int k=first[x],v;v=end[k],k;k=next[k]){ if (mark[v]) continue; P[v]=1; Dist[v]=value[k]; Belong[v]=v; A[++Num]=Pair(Dist[v],Belong[v]); Dfs(v,x); } sort(A+1,A+Num+1,cmp); int Ans=0; int l=1,r=Num; for (;l<r;){ for (;A[l].st+A[r].st>K;){ P[A[r].nd]--; --r; } if (l>=r) break; Ans+=(r-l); Ans-=(P[A[l].nd]-1); P[A[l].nd]--; ++l; } for (int k=first[x],v;v=end[k],k;k=next[k]){ if (mark[v]) continue; Focus=0; Search(v,x,size[v]); Ans+=QAns(Focus); } return Ans;}int main(){ scanf("%d",&N); for (int i=1;i<N;++i){ int x,y,z; scanf("%d%d%d",&x,&y,&z); Add(x,y,z); } scanf("%d",&K); Dfs(1,0); Search(1,0,size[1]); printf("%d\n",QAns(Focus)); } |
评论 (0)
