@OceanEye7年前
04/28
20:39
久违的1A
题目很裸……当年的男人八题现在看来也不过如此吧。
题目的数据范围给的不是很清楚，所以就没有用树状数组用了快排。
每次分治的时候要取重心来保证复杂度。
恩还是有些地方比较傻逼的
没有卡常数
|
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 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 100010 struct Tedge { int to,val; }edge[N<<1]; #define TO edge[i].to #define VAL edge[i].val int NXT[N<<1],fst[N],e_tot; void add_e(int a,int b,int c) { edge[e_tot].to=b; edge[e_tot].val=c; NXT[e_tot]=fst[a]; fst[a]=e_tot++; edge[e_tot].to=a; edge[e_tot].val=c; NXT[e_tot]=fst[b]; fst[b]=e_tot++; } ll ans; int n,k; bool use[N]; int dist[N]; int siz[N],T,mx[N],root,v; int d[N],tail,b[N],tot; void pre() { read(n); int _,__,___; memset(fst,-1,sizeof(fst)); for(int i=1;i<n;i++) { read(_); read(__); read(___); add_e(_,__,___); } read(k); } void dfs_calc(int x,int f) { ans+=2; d[tail++]=dist[x]; for(int i=fst[x];~i;i=NXT[i]) { if(use[TO]||TO==f) continue; if(dist[TO]<=k) dfs_calc(TO,x); } } void dfs_add(int x,int f) { if(dist[x]<=k) b[tot++]=dist[x]; siz[x]=1; for(int i=fst[x];~i;i=NXT[i]) { if(use[TO]||TO==f) continue; dist[TO]=dist[x]+VAL; dfs_add(TO,x); siz[x]+=siz[TO]; } } void getroot(int x,int f) { siz[x]=1; mx[x]=0; for(int i=fst[x];~i;i=NXT[i]) { if(use[TO]||TO==f) continue; getroot(TO,x); siz[x]+=siz[TO]; mx[x]=max(mx[x],siz[TO]); } mx[x]=max(mx[x],T-siz[x]); if(mx[x]<mx[root]) root=x; } void dfs_solve(int x,int f,int coc) { T=coc; root=0; tot=1; getroot(x,0); dist[root]=0; for(int i=fst[root];~i;i=NXT[i]) { if(use[TO]) continue; dist[TO]=VAL; dfs_add(TO,root); } sort(b+1,b+tot); for(int i=fst[root];~i;i=NXT[i]) { if(use[TO]||dist[TO]>k) continue; tail=1; dfs_calc(TO,root); sort(d+1,d+tail); for(int j=1;j<tail;j++) { ans+=upper_bound(b+1,b+tot,k-d[j])-b-1; ans-=upper_bound(d+1,d+tail,k-d[j])-d-1; } } use[root]=true; for(int i=fst[root];~i;i=NXT[i]) if(!use[TO]) dfs_solve(TO,f,siz[TO]); } int main() { pre(); mx[0]=INF; dfs_solve(1,0,n); printf("%lld",ans/2); return 0; } |